My two pesos
IMC, the paladin wouldn't have been stripped of his powers. He stopped someone in the middle of an obviously evil act; at least not the first time.
However, he would have faced censure and light punishment from his order or church, perhaps little more than a stern lecture on the virtues of due process and providing the wicked a chance to atone for their evil ways. Or perhaps he has to spend a few days aiding the temple clerics healing the sick and injured so that he might further contemplate on the virtue of mercy.
The leader of his order would make absolutely clear to him that even the most wicked mortal can seek repentance, and that there are laws in place for such situations, and that attacking with such force and duplicity are not the ways of the good heart. But I wouldn't have his god strip his paladinhood.
Now, if this were a common occurance, then, yes, I would strip him of his paladin abilities. If such situations happen often, then you have a sociopath using a facade of virtue to hide his dark heart.
Even if, for some reason, I did strip him of his powers, I would allow him to atone for his misdeeds.