Get some Bandits and hang up the Paladin to a tree or something and wait. He will beg for some damage or die from thirst.

Or - maybe more fictional for the paladin - his many uses of "Bloody Aegis" makes his deity angry. Maybe he will send the Paladin to a quest to show his loyalty.. and one vow is "don't use Bloody Aegis".