One question that has not been addressed is exactly why atonement and loss of powers is coming into it. Clerics are not paladins. They do not have a code of conduct. The only rules-based punishment that I can think of is saying that his alignment has slipped to LE and he can't worship his God anymore until he has his alignment restored.
Destruction isn't an Evil spell, and it wasn't cast with Evil intent. There are plenty of reasons listed above for deciding that the act was evil, or not so evil.
That said, I can understand wanting his God to take exception, IF the player is aware that such things could happen as a result of his character's actions. I'd probably go for something simple like having an Avatar appear to him with a tongue-lashing and a strong warning about ends and means. For anything stronger, like the suggestions above about changing damage spells or losing domain powers (cool ideas, imo), I would want to work with the player on what he thinks should happen. Players shouldn't be punished for making difficult decisions, even if it makes sense for characters to suffer. If the player isn't going to have fun roleplaying being on God's bad side, you're better off just sticking to a heavenly warning. A celestial babysitter for a time might not be a bad idea, either. If the player thinks it'd be fun to have a great redemption storyline, go all out.
The tempted by Hextor thing could be good no matter what punative measures you take against the character. Don't force him to change gods, but have representatives start showing up trying to talk him over to his side. Signs start appearing around him. Perhaps he suddenly has access to powers or spells that clearly don't come from Heronious, and his attempts to get an explaination from his god don't work. Heronious is testing him. If he gives in, THEN his god turns away. However, he may begin to more fully appreciate the true nature of his actions if the evil god thinks they were really cool.