My suggestions to help out the high level Paladins. Hard to find a happy medium which doesn't break other classes. I choose abilities that feel iconic Paladin, or imo at least. All but one are enhancements. Tweak feedback desired.
Champion of the Light (Granted class feat at Level 5)
At 5th/8th/11th/15th level, you gain +1 to attacks and +2 light damage against evil creatures. This replaces the Paladin's mount ability. This gives you +4attack/+8 damage to all evil creatures, which is a major portion of the game.
Enhancement
Levels 7/10/14 1/2/3 ap
Adds +2 light damage each
I went with light damage because +8-14 crittable damage seemed to much. Could use regular damage with +1 instead of +2.
Shield Mastery
Levels 4/8/12/16 1/2/3/4 ap
Adds +1 Armor class when using a Shield.
Fighters should get this as well, and it should stack with tower shield mastery. Would help with the current dps/ac issues.
Sword Mastery
Same as Racial
+1/2 to hit and damage with Longswords, Bastard swords, and Greatswords.
Torn on this one, what do you include? Would you mind it being an option even if you weren't specced for one of choices?
Fear enhancement changed to:
Same levels and ap
1st ap gives a 5' fear immunity aura around the Paladin. 5' increases per point.
Better then current one, yet not really overpowered with end game items and gh.
Concentration enhancement needs changed. I was thinking maybe it could add to Diplomacy as well. Since Paladins don't get intimidate, we could work around this by increasing everyones Diplomacy. Would it be used by the high end zergers, doubtful, but would be better then current implementation.
All I have for now.