I read the initial post and skimmed the responses, and responses to responses.
First rule, it's a game, try to have fun. If character A doesn't go with group B, stop and change.
That being said, what's lawful about being a fanatic and attacking people who have broken no laws? If you kill someone who you deem 'evil' that's still murder from the viewpoint of the local sheriff and magistrate. Indeed you could even 'justify' killing them in their sleep, since they would pose less of a threat. I would politely tell the Paladin, his god may be pleased with him slaughtering some heathens, but that will be cold comfort in the gallows.
The DM's role is not only to play opponents but to represent the society, culture and country the player is in. A Paladin should be zealous, but not a zealot. Pride and wrath are two of the seven sins.
Perhaps you as the DM could lead the character to a better way. An older mentor could explain that patience and humility would go a long way to finding a better way. Encourage the Paladin to watch and 'keep an eye on' the suspicious characters.