we need more information

the character's race
his stats
his feats
what we can change
the party he's in
what's available, what's banned (if anything is, if not point it out)


but , to work with what I know

feats:

from smite to song (change your smite evil attempts into inspire courage like a bard of equal level)

alternate class features that could help

holy warrior : lose spellcasting, gain extra feats (from complete champion)

suggested extra feat (it's a limited list) : extra smites (for extra songs) or whatever helps you qualify for a build

stand fast : lose mount, give divine grace bonus to all party members within 20 ft (only 1 bonus at a time though: ref, will or fort)

with only 5 levels of paladin, the mount won't be useful for long


suggested build

from smite to song + dread pirate (the honorable version)

dread pirate has an ability that stacks with inspire courage (which you get from smite to song), should work well with your player's ideas

you might want to change some of the requirements (many are nonsensical) or allow flaws to help qualify