Does the player want the paladin character back? Are they cool with a little side adventure before that happens?
A couple of ideas:
You can take the Buffy the Vampire Slayer (tv show) route. In that show, when someone was turned into a vampire, they actually died and a demon inhabited their body complete with memories and everything. So you can do a possession similar to that. The demon can possess the body (or any demon/ghost really and be a minion of the demon). The possessed paladin then goes on a villainous streak using the identity of the paladin, using his personal knowledge of the party to really mess with them. The player can even assume the new identity and play in the party for a while as the possessed paladin and lure them in a false sense of security. Make up some reason they came back, like the fleeing enemies ran into a group of clerics who battled them and recovered the body. It can all be a made up story, just something that's feasible. Once the paladin is recovered and has his body back, he rejoins the group for real and has to undo the damage his possessed self caused.
Clone him/make a construct of him. Say they get the paladin back and everything is right in the world. Then tales of him start spreading about the evil things he's done. There may be bounties out for him. People are afraid of him and swear they've seen him before, even though he's never been to wherever they are. Perhaps the party only got a piece of the paladin back and used it to raise him, so the false version has some kind of tell, like missing the finger they used to raise the paladin. Create a nice little villain for the paladin that knows everything about him.
Have the paladin haunt the party until they get him back. His ghost appears with cryptic warnings or they see him passing a doorway in the night. In reality, the demon managed to trap his soul somewhere but when the demon loses focus, the paladin can get out briefly to warn his friends. It could give the party some leads about what to do next if they are stuck or how to find the demon if they are lost.
Side note, I once played a paladin that unknowingly had an evil twin. The evil version worked behind the scenes to mess with me until I learned about him. It was very fun. The hook of the game was that reality wasn't what we thought it was. We were really in a prison run by mindflayers who were trying to pry some dark secret from our minds. We learned something maddening (very H.P. Lovecraft) and it broke our minds. What we learned was something the mindflayers needed to invade our world. We escape the prison and my paladin learns that not only was he close to his goddess, they were actually lovers. My goddess refused to let any sin taint her perfect paladin, so she took it from me. That sin had to go somewhere, so it became an evil version of me. An anti-paladin made entirely of sin who knew everything about me. It made for an awesome villain. So I think using this opportunity to make a fun villain for the player of the paladin could be fun.
