Well, I'm going to apply my own little litmus test and see where I come out on this one. (Honestly, I could go either way on this question, which is why I find this example helpful to go back to.) What would the cops of Law & Order do?
Well, baby-killing is illegal, at least in New York where the series takes place. But we're being a little disingenuous to call them "babies". Babies wear diapers, suck their thumbs, and occasionally leak onto your nice black shirt, the one that's casual, but you can wear it in nice restaurants. Carnivorous tadpoles who live in barrels and devour human flesh aren't really "babies" in the conventional sense. There are some species that just don't go through a harmless phase (like baby vipers, who are unable to regulate how much poison they put into a bite and so are actually more poisonous than adult vipers).
Ballparking it, these things come off sounding more like rabid dogs than babies, which means they should be put down in the interest of public safety. You could make the argument that they are intelligent, but that won't work for me since I'm a dog person and I already think dogs are smarter than people. Plus, if they are like rabid dogs, why is the fact they are intelligent make it better. Which would you rather have running around town, rabid dogs, or rabid dogs who can use doorknobs?
As a GM, here's what I'd do. I wouldn't tell the paladin's player anything definitive, and no matter how many times he cast Augury or rolled Know: Religion, he'd get the vaguest of platitudes. And then, if the player really thought about it, weighed the options, and picked the course of action he felt was the most appropriate according to the paladin's code, then that would be the right thing to do. If the player was roleplaying, I'd leave it up to him. If he wasn't, the gods would frown upon his efforts. ("He chose... poorly.")
I think how the players make their decisions are more important than what they ultimately decide. (Even if I disagree with it. Running the game doesn't make me the final arbiter of morality.)