Some thoughts:
1. Paladin spells get much more interesting in Complete Divine / Magic of Faerun. Remember that most paladin spells set out in MoF were "grandfathered in" by PGTF.
2. Paladins are *horrible* multiclassers. Unlike wizards, who get all of their powers plus a ball of wax when they go into a PrC, very few PrCs let paladins continue to progress in any of their skills. I actually thought about the Kensai as a Paladin variant for a while -- but your player is right, more than two levels in it is too much.
3. So, what are your options? Fist of Raziel permits spell progression and smite progression, and gives some pretty nifty abilities related to smite along the way. Most importantly, the feat requirements are pretty low (servant of the heavens and, I think, either power attack or weapon focus).
Another route that I think might be equally interesting is Templar. There, though, the skill requirements are murder. It might require some reworking of the character to get you into the class. But the class has full paladin spell progression (although the two don't stack, who cares -- you get a double complement of the low-level paladin spells which are the good ones anyway). More importantly, you pick up two (maybe three?) bonus feats, plus weapon specialization.
And the best bit is that you get extra smites that stack with your paladin levels, AND you get Mettle, which, combined with divine grace, really gives your saving throws some teeth.
Paladins are very fun. They are not, however, easy to play, nor are they balanced (3.5 gave it to them in the shorts: Holy Sword got nerfed, turning got nerfed, spellcasting got nerfed, and they got Summon Mount as a consolation prize). But if well done, they are a valuable and flexible addition to the game. I rarely play anything else.
best,
Carpe