I think of it like this:
Ten college students accuse a marine veteran of robbing an old woman and demand that he give them her purse back, when he doesn't, one of them hits him with a 2x4 so the marine kills half of them. He explains to the court that they are "murderers" and he was just defending himself. I don't really think that is going to help his cause. Nor do I think society would be on his side. Killing them is a lot different than beating the crap out of them.

They also never demanded that they hand over their own valuables or their own coin purses. They just demanded that they hand over the woman's coin purse. They also did this in the middle of an open busy street. That's not exactly what I would call a "mugging".

It was obvious to the PCs that these guys were no threat to their level (9th). The PCs were not scared of being outnumbered. They reacted with violence because they were cocky and knew these guys posed no threat. They didn't "defend" themselves because they were worried about being killed. They just used "being outnumbered" as an excuse to kill them. The players also know about nonlethal damage and I was clear when the NPC made a nonlethal attack with the blunt end of his weapon.

I considered if these guys knew he was a paladin, but he crafts his own armor and his choice of attire doesn't make it clear that he's a paladin. He could be mistaken for a cleric, a knight, or just any random soldier. Even so, the fact that the men tried to intimidate them into handing over the purse and the paladin responded back with intimidation and threats rather than diplomacy wouldn't help identify him as a paladin. I determined that nothing about him at the moment made these men feel that they were in the presence of a respected and morally just man any more than they thought they were being themselves. They were honestly trying to help a young woman. Think of the NPCs as bikers at the bar that step outside and see some guys pushing around a helpless girl so they go to her defense and will beat the guy up if necessary. FYI, this was a scenario created for the adventure. I was in no way using this as a test to the paladin code. I wasn't even thinking about it until after the encounter.

I understand PCs are prone to killing anyone that looks at them funny and coming up with any reason to defend the action. Even though the other PCs probably committed murder here, in game context, it could still be a tragic mistake on their part as far as I'm concerned. They are used to being betrayed, fighting evil, fighting neutral monsters, and even fighting CN people from time to time. It was an unexpected situation and it could be looked at as a rash decision on their part in the heat of the moment. I have some legal courtroom drama planned for them just for fun, but I don't think I'll change their alignment for this. The paladin on the other hand is a different matter since he in no way even tried to uphold the city laws or his own moral laws here. He just Judge Dredd'd them. Asking for someone's money back is not exactly breaking any laws.

Thanks for all of the very well thought out responses. I just wanted confirmation that I had a logical and fair reason to deal with the paladin's actions and it looks like I do. I'm not trying to be a vindictive DM and removing his paladin abilities will actually be a burden on my DMing since it screws with the CR of some upcoming tough encounters. I do however want players to uphold the flavor of their class or play something else if they are not willing to do that. Hopefully I can make this an interesting scenario for him to play out so he doesn't feel like I'm simply just trying to screw him over. He killed the NPCs, not me.