While it is true that the Romulans bulldozed a world in an earlier "post-ENT" novel, and that the Klingons would later sterilize a planet (albeit an uninhabited one) in TNG's "The Chase", I might still argue that there is a difference between what it means for the two empires involved.
By and large, the Romulans are/were strongly isolationist and xenophobic, and were likely seen as a "rogue state" by most of their neighbours. Their acts of xenocide could be treated in this manner, and not taken as the norm across the rest of known space.
The Klingons, in contrast, are much more "plugged-in" to the broader interstellar community - even if they often view it as ripe for conquest, they still conduct trade and diplomacy with others on a fairly regular basis. While there is no "space Geneva Convention" for them to sign up to (or not), their actions help define the unwritten "rules of war" which are undertaken by those under their influence. For them to decide that despoiling ecosystems is fair game in times of armed conflict means that the door is being left open for others to react accordingly - which ultimately puts worlds like Qo'nos itself at greater risk. (If not directly, perhaps by someone launching a suicide run at Praxis, aimed at triggering that moon's collapse a century early?)
But then, I wonder about the Federation's reaction to this Klingon act of world-killing. So long as the colonists were evacuated safely, it seems that no serious long-term sentiment was held - save perhaps for a brief sigh over the fate of the now-doomed indigenous life-forms. (Perhaps this is why the fore-warning was so important - had the colonists still been on the surface in the event of such a suicide run, there might have been a much larger sense of outrage back in "core" Federation space.)
In a broader sense, it's perhaps a telling sign of the nascent Federation's weakness, in that it seems to exist to a large extent at Klingon sufferance. Had the Empire gotten serious about smothering the UFP in its crib, there isn't much that Starfleet, or anyone else, would have been able to do to stop it. Which, I suppose, is somewhat fair; it will take time and effort for the Federation to evolve into the more robust entity portrayed in the 23rd and 24th centuries.