The combination of Secular Messianism (or Wilsonian Idealism, or whatever you want to call it) with Machiavellianism may seem paradoxical, but upon reflection I am of the opinion that is there no contradiction between the two. In fact, in practice they are often closely allied.
Machiavellianism has solely to do with means, not ends. A man may use machiavellian means to enrich himself, or he may use them to try and bring about utopia. Secular messianism, by contrast, has chiefly to do with ends. It involves trying to radically alter the social order on the belief that doing so will create some sort of utopia. Messianists have tended to be machiavellians, for they believe that the good involved in creating their new society is so great that any short term negative effects, be they terror, torture, murder, or lies, are all justified as a means of hastening it. Thus, you have people like Robespierre, who could talk constantly (and sincerely) about virtue while at the same time implementing the terror.
None of which is to suggest that Mark is right in labeling Neoconservativism secular messianist or machiavellian. Numerous paleo statements to the contrary, the neocons are not actually messianists. Nor as a rule are they machiavellians, though some, such as Michael Ledeen, do seem to be influenced by him.
The reason I view Mark's comments as being contradictory is that I see Wilsonians as having a very different view of human nature than Machiavellians. For Wilsonians, the generally have a very high ideal of what humanity can become within what they see as the proper societal framework. While calling Kant a Wilsonian is an anachronism, he seems to me to have sketched out this concept pretty clearly with his idea of Perpetual Peace. I have my own problems with Kant that we need not dwell upon, but it strikes me that this idea of human nature is quite different from that of Machiavelli, who argued (and I am being incredibly simplistic here) that men are far more likely to evil than good and that if you want to get ahead the best way to do so is to do evil to the other guy first.
Regarding all the bloodshed that messianism of various stripes have formented, I would distinguish between the worst forms of utilitarianism and Machiavellianism. Machiavelli, at least as I read The Prince, has no lofty goal or desired end-state. It is written as a guide for how to obtain and maintain power, which here again strikes me as quite a different mindset than those of sincere revolutionaries who honestly believed that they were working for a better world. If nothing else, one could convince the former through reason or persuasion that their power did not require brutal actions, whereas nothing would persuade the latter. The Blackadder mentions Robespierre, but no doubt he believed that he was engaging in virtuous activity while he was implementing the Terror.
In the case of the neocons, they either believe what they write about the spread of democracy or they do not. Many paleocon writers, near as I can determine, do not believe that they do and instead hold that much of the democracy rhetoric is little more than a smokescreen of their true goal of removing the enemies of Israel. If that were the case, then they would indeed be Machiavellians or at least utilitarians, but it strikes me as fundamentally incoherent to argue that they are both simultaneously.