This isn't about combat necessarily. This about introducing morally "grey" NPCs that have a point that he can see. It's about breaking down his pride a bit.
Noble House
He's the last heir of a noble house--but there's no way his house is blameless. If he's got a moral code that he follows, introduce someone that's been wronged by his house in a way he wouldn't forgive if he were not part of that house. In fact, you can introduce a plotline wherein he has to right the wrong done by his own house. The grey character through circumstance (a crumbling cliff, lava, whatever) might end up having to let him go, but the incident, and finding out about what's been done should be a blow to him psychologically. Alternatively, he'll win the fight, but now he's got questions about his family's honor. Further, his house might not be the only one involved in this horrible thing--that's when you present another, still powerful house that's involved or was involved in the past. Maybe, if he kills the grey character, there'll be clues to that effect on the body.
The other house worked with his for generations and together they did the horrible thing (this can be slave trade or anything else you can think of). But he's known these respectful, noble people for a long time. Some members of the house don't know about it (especially a younger daughter or son) or have felt powerless to stop it. After all, patricide isn't a noble thing to do...ruining your own house isn't either. Maybe the reason his own house is gone is that someone in it developed a conscience, and he's just discovering that now.
But, despite whatever evil house 2 has done, they are part of the community, a vital part, and they do good throughout the land. If said evil thing is known, it will result in the house's death. Include adorable toddlers in house 2, and maybe even an eager squire that copies everything your paladin does. Basically, make sure that the children, and his being treated oh-so-well and honorably by this other noble house is laid as the ground work before. Make sure he has relationships with these people and likes them.
This scenario is much more of a gut punch and will lead to more maturity than just, say, a powerful, unbeatable foe. Although, you can also introduce that--the patriarch or matriarch, if he confronts them, should be powerful. And, once they put him and the party down, but not killing them, they should say something like "I will not kill the last of your house here today. But consider deeply the consequences of your actions. You've done much good, but the past is in the past." The noble can lie about not doing the horrible thing anymore, of course, and that they've killed the rest of his family. Evil can have a code, and not seem all that evil. Seriously, have noble family 2 treat him respectfully and give the party good and noble missions.
Repercussions should be clear, and they should not just be combat-based. Losing that noble family might clear the way for a take over from a more evil set of nobles near by. Peasants might depend on their charity and so on and so forth. The telling of this tale might lead to the disgrace of the paladin's house.
The above is just an example of what you could do to foster character development. Basically, a paladin might see in black and white, but they have to know that they live in a grey world, where even the right thing might not be a good thing.
Other things you can do to drive the message home is:
Have a character they admire, for example a legendary paladin, who is much
more tolerant of the foibles of others.
Have characters that aren't "good" do good things. "World I live in
you don't survive by folks seeing you nice."
Take a part of the concept of honor and the system that's in place. The
simplest person should have something to teach him. A thief should
have something to teach him. In fact, you can have a thief rob him
and also help him. Lovable rogues and all that.