Generally, I would use sich aufmachen without naming my destination.
Ich mach mich jetzt auf. Wann kommst du nach?
But reading the question I acknowledge that it can be used with a destination aswell. Rogermue uses a nice, biblical example:
Sie machten sich auf nach Bethlehem.
And I would likely also allow (among others!)
Sie machen sich nach Bethlehem auf.
The thing about your market example is that it’s missing a preposition as Emanuel pointed out in the comment.
Er macht sich auf den Markt.
sounds funny. It’ll either mean he is making himself onto the market (as in on the top of the market) or it’ll mean he is opening the market for himself, but that would have a better word order as you asked
Er macht sich den Markt auf.
To give the sentence the meaning you intended, you need an auf from aufmachen and another one from auf den Markt to give:
Er macht sich auf den Markt auf.
Compare with the perfect tense:
Er hat sich auf den Markt aufgemacht.
And this is personal preference, but I would prefer
Er geht jetzt los zum Markt
or something like that.