My experience has been that, in practice, the fighter mark blows the paladin mark out of the water.
For one, the fighter mark can actually interrupt the target’s attempted action (in the case of a shift). Whereas an enemy marked by a paladin that really wants to shift and attack someone else can just take the damage, or he can shift one and flee and not take any attack or damage, which the fighter mark would stop those shenanigans.
Second, the fighter mark is much more powerful against artillery, controller, skirmisher, and any other character that predominately attacks at range. The paladin mark can’t really do anything about the shift one and shoot strategy. The fighter mark can singularly destroy many creatures entire ability to attack by preventing them from shifting to get out of provoking for a ranged attack.
Third, the fighter mark is free. The paladin mark takes a minor action. This may not seem like a big deal but it can be.
Fourth, the fighter gets to mark as many guys as he can attack. This can reliably hit everyone adjacent to him and in the case of dragonborne, half-elves, and some multi-classing can consume entire groups. And he gets his free attack against any of them that are adjacent not just one. The paladin mark on the other hand only targets a single enemy. The paladin can mark others with certain powers, but still only gets the DC damage against one of them.
Fifth and final, the fighter attack tends to average more damage than the paladin mark. There is a roughly 50% chance of missing, but even taking that into account 3 + charisma v [W] + strength + feats + enhancement is pretty impressive, and against a paladin who focused on strength it is downright comical how much more threatening it is.