Simple Law vs Good conflict.
A paladin of most sorts could probably pardon them(small infraction vs excessive punishment), but I can see a scenario where their means of survival is assured(e.g. finding a job where he can provide for his family) and then cut his hand off.
And then take him to the temple and pay for the hand to be regenerated.
Punishment is performed. So is mercy.
Another classical example might be a Paladin in a Lawful Evil society. Said Lawful Evil society demands all elves be killed on sight as a law. Paladin has an elf for a travelling companion. He certainly isn't going to fall because he refused to kill his companion, even though this clearly represents a breach of the laws of the society he's in. And he certainly won't fall for trying his best to enforce breaches of this tyrannical law - he's acting in the interest of defending life, after all.
Back on topic, I'm not sure how 'shady' his actions are as related to good. Considering that:
A) The creatures were of Evil alignment.
B) Other Astral Stalkers had already been hired to do the party in.
C) The likelihood of them surrendering peacefully and undergoing trial was, at best, slim.
D) The Paladin in question would actively rebuke the use of a law system so he wouldn't care for C) anyway.
Pre-emptive smiting may be harsh (as it is a preventative measure rather than a punishing one, and paladins as a rule can't see the future), but in this particular case it was likely justified. If they're hired to kill an adventuring party with two paladins in it (and neither is a Paladin of Tyranny), then they probably aren't very picky about their targets. Which means they might pick up a contract that involves killing defenseless people, for example.