Misty step does help, but it isn't available until level 5 and there is a high cost to using it at low levels because you have very limited slots.
A few other things to consider in this discussion:
1. The fighter gets a 3rd attack at 11th level and this is a pretty big deal when combined with GWM or other fighter abilities. He gets a 4th attack at 20th level, but that is not that great (and neither is the Vegence Paldin's capstone IMO). The 3 attacks per round means that combined with action surge a fighter can do a crap load of damage if he goes nova in round one - 6 attacks in one round plus 5d10 battlemaster dice (and their effects) or 10% critical. This will usually be more damage than a Paladin can deal in round 1. A 11th level battlemaster with a greatsword going nova that hits with all 6 attacks and no criticals is going to do 12d6+5d10 (81.5 average including reroll 1/2) vs for a Paladin 4d6+8d8 (59.7 avg including rerolls). After a short rest the battlemaster can do it again. I get it that a Paladin can wait for a critical to use his biggest smite, but then again if you are fighting someone that you need to go Nova on you usually can't afford to wait for a critical.
2. If you roll your abilities you are at the mercy of the dice, but on a point buy the Paladin needs to buy charisma and needs to use feats maxing it if he wants that +5 aura. By comparison the fighter will have a a better combination of strength/dexterity/constitution to start with and will be able to take more martial feats. This will mean better to hit rolls, slightly better base damage and/or more hit points. It also means all else being equal the fighter will be better at athletics (or acrobatics) which are used in almost every battle. The fighter will spend less time on the ground or restrained.