You could offer them a favour if they let the Paladin go - also you could point out that by letting the paladin go he would presumedly go onto do greater feats and so appreciate in value so if they deserve him he might return of his own will later.
So they a) get a favour - within reason - from your party and b) have the chance of a far greater prize down the line (likely subject to how they treated him).

That far greater prize is likely the better angle with the favour being merely how they hedge the bet.