Killing the character is so... straightforward. It lacks imagination, and imagination is what D&D is all about. Also, just killing them would rob you of a chance to do every DM's favourite thing: put your characters through hell.
Notice, that's the character going through hell, not the player. If done right, the player will love it.
Talk to the player and figure out exactly what the gap is between what the character is now, and what the player would rather be playing. It sounds like you have a pretty good handle on this already.
Then, see if you can find a way to close that gap.
Tell the player that you're going to try to do this. Don't tell them how you plan to do it, but you could drop hints if you want. So, the player dislikes the Lawful Good element? Which do they dislike most? The Lawful, or the Good?
If it's the Lawful, then put them in tough spots where their laws are forcing them to do something that they have in-character reasons to not want to do, or where their laws conflict. Random example: an NPC is trying to find out who killed their father, and have vowed to kill whoever it is. The paladin knows who did it, but it happens to be someone the paladin respects, and they did it because the father was secretly evil. The paladin can't lie, but he also has to uphold justice, so now he has a problem. If he tells the truth, someone innocent may be killed, but if they lie, then they could prevent an unjust death.
(Yes, this is basically the tale of Spiderman/Green Goblin/Harry Osborne. Any good plot deserves to be stolen and turned into a D&D campaign.)
If it's the Good, then put them in tough spots where their good alignment forces them to do something they don't want to. Random example: an ancient and powerful curse is awakened, and threatens to unleash hellish destruction on a whole town... unless an innocent life is sacrificed somehow. And lo and behold, the party - particularly the paladin - ends up in the right place, at the right time, with a suitable NPC available. If they kill the innocent, it'll haunt them, but they'll save the town. If they spare the innocent, then they have a lot of work and a lot of deaths to contend with.
If it's both, then do both!
Now comes the important bit: with enough of these big tough situations, their alignment can shift. This takes a while, which is why it's important to tell the player that it'll be happening and explain that it may take a while, but it'll be worth it and you'll make it as cool as you can. That way, they hang in there, waiting for the next step on the road, reshaping the character as they want them to be and generating a really cool story about the terrible hardships that broke the paladin's spirit, causing him to forsake his vows and his code of conduct, and... well, your player gets to choose what happens next.
We have this happening with multiple characters in our current campaign. We have a wizard whose lust for power is slowly driving him to forsake his friends and commitments and slide towards the Dark Side... I mean, Chaotic Evil. We have a rogue who's been through such hardships with the party that it forged incredible friendships, eventually inspiring him to disregard his own interests to selflessly risk himself to save his friends, shifting him towards a Good alignment. And we have a bard who has seen one too many comrades die despite her best efforts to save them, and is slipping into madness and becoming increasingly Chaotic, doing whatever it takes to keep the party alive.
When done well, character evolution is an incredible driver of good plot and player enjoyment. You've got some real potential here; work with your player to have some serious fun with it.