One other thought: Paladin of which god? Not all gods are Lawful Good. Some are just Good. Some are just Lawful. There may be some wiggle room there. See the item referenced about how to play a Paladin without being a goody-two-shoes.
However, storytelling and role-playing are important. You have a character here who, for reasons that seemed good at the time, dedicated their life to the service of a deity in nearly the same way that a cleric has... and who, like a cleric, has the deity looking at them particularly closely to grant the the benefits of that dedication. If they start failing to meet their side of the bargain -- if they stop trying to live up to their god's ideals -- the best they can hope for is for those benefits to start failing unexpectedly, perhaps at the worst possible moment, as the god decides they don't deserve special treatment. The god may even start swatting them with penalties -- curses rather than blessings -- in an effort to drive the point home. This is the "Fallen Paladin" approach.
"I'll just switch gods, and ask my new god to protect me"? Again, for someone who is a strong enough believer to have gotten the god's attention in the past to make a move of that sort is likely to Seriously Piss Off the previous deity -- more so than simply losing faith. And, again, role-playing: How often does someone suddenly change their entire belief structure, without serious psychological damage either causing it or caused by it, especially in a world where it's very clear that belief has concrete manifestations? This sounds like a possible basis for a Boss-level opponent's motivations, but it's going to take far-above-ordinary playing skill to make the character someone whom the rest of the party is going to want to have around.
But frankly, the best answer when you have a character whom you really don't like playing, and for whom you can't find an in-game and in-character reason to play differently, is for them to find a reason to leave the party and to roll up another character to be recruited as their replacement. If the GM is feeling kind, maybe the new character can start at a level comparable to the rest of the existing party. A friend of mine once decided he didn't like his Thief, and basically let the thief get careless about seriously backstabbing the party. He got caught, we declared that only a rat would abuse his friends that way, and he was put under a geas to walk ahead of the party and check for traps for the rest of that adventure. A trap he didn't find killed him, we said "good riddance", and when we got back to town we recruited someone else (and interviewed them Really Carefully this time, and didn't tell them what our real ultimate mission was until we were sure we trusted them.)