It depends on what happened in the story.
You could change the wording "Evil" with "Good" or better, "Any - enemy - of - mine", but it's too general.
What are these evil acts?
Is the Divine Patron Angry? How has He/She made it manifest?
Has the Paladin lost his powers (I suppose not)?
When this is all clear and explicit, you could make up a Compemdium Class, much similar to the Paladin, but geared towards your game.
If the Paladin becomes like an "Agent of Evil" (Stormbringer), you change the Quest move into something more focused (Slay - Steal - Destroy...), as he roams Dungeon World to quest in favor of his new master.
If the Paladin is just disgraced, he simply loses the move, gaining another; maybe a third version of Quest, in which HE is the power behind his inner strenght (like a Ronin).
Assuming the evil deeds were a choice of the player, you should not make the change sound as a punishment:
"Paladin, you fell from grace, SO you become this super cool Antipalaldin, hated and despised by you former peers. What do you do?"
Maybe this is a decent example of how to snowball things in the game, to keep it moving.