A spiritual dimension
I don't know if you permit evil PCs. (I don't, so this would potentially be a trip to NPC villaindom in my campaign).
The premise:
-The character is already being tempted by evil. Why else would he abandon his code for a few paltry hunks of metal? Why would he deny the barony the equipment it could use to defend its people? Why would he steal from the widows and orphans of his companions?
-So, since he's already begun to give in to temptation, why would it end there?
The Beginning:
The character finds that he's lost some of his powers (he's really lost all of them but how does he know he's not immune to fear anymore or that he doesn't have divine grace or divine health?). This much is a necessity. The character has violated about half of the explicitly stated minimum levels of the paladin's code in the PHB. As the player of several paladins, I wouldn't expect them to keep their powers after this. The next time he stops into his church or his order, he finds a priest preaching on honesty or a holy book open to the words "Thou shalt not steal" or something like that.
If the character immidiately repents and seeks out atonement fine. Otherwise, proceed to act 1.
Act 1.
The paladin is presented another chance to lie and steal. Walking throught the street, he finds a heavy purse with a lot of gold and a sigil embroidered on it. If he identifies the sigil and gives the purse and its contents back, he escapes. Otherwise, continue: a young woman wearing a signet ring with the same sigil as the purse approaches him or his companions. She seems very distraught and is asking everywhere about her purse. She should seem sympathetic but not so sympathetic that the ex-paladin would think he'd be starving 10 children and sentencing her father to debtor's prison by keeping the purse. No need to give his conscience too much ammo. (The woman is actually a demon/devil/evil cleric with trickery domain who left the purse deliberately to tempt him. He'd know if he were still a paladin but now his detect evil isn't working--not that you tell him that. He just concentrates and doesn't see any evil auras).
Act 2.
A merchant, prince, or superior (actually the same demon or a different one) approaches the ex-paladin to guard a shipment of goods or a chest of gold for a time while he negotiates. It should be clear that the individual is somewhat shady (if the paladin assumes that the gains are ill-gotten, let him). If the paladin takes some of the money (the chest isn't locked or secured), proceed further.
Act. 3.
Now that the ex-paladin has demonstrated a reliable weakness for wealth, have the shady individual approach him again. This time, he's asked to do something slightly against the law and slightly evil for good profit. (Maybe breaking some kneecaps to "encourage" someone to engage in a "business" deal or something like that). Maybe it's twisting an oath or agreement he's made in order to pervert its intent and pervert justice. If he accepts, his paladin status may no longer be gained by atonement. Proceed further.
Act 4.
At this point, it should become clear that his deity has abandoned him completely. Maybe he develops a disease. Maybe healing spells no longer work properly on him. He's approached by someone who offers to cure the disease/heal him (again, the demon/devil/evil cleric (with trickery domain) mentioned earlier). During or after the healing, the tempter mentions how he's been treated unjustly by his god. He didn't do anything wrong after all. If the character mentions the theft, the tempter assures him that it's not a big deal--anyone would've done the same. The tempter should offer justifications for his actions--the baron was just going to keep the money for himself; the girl was rich and didn't deserve the money; the dwarf would do much more good for more people with the money, etc.
Act 5.
The tempter should develop a more open relationship with the dwarf, encouraging bitterness and justifying the dwarfs actions. When the time is right, the tempter offers the character some of his powers back. ("here's a chance to get back at that deity who treated you so unjustly, etc.") If the dwarf accepts, he's an ex-paladin blackguard. Otherwise, he may be an evil fighter of some stripe. Or maybe, he'd be on the road to redemption (although not the regaining of his powers. . . .)