Another option (which I'm partial to) is something like "the enemy of my enemy is my friend".

Not everyone is on top of who's part of the mercenary company and some people could just see this as "a change", so they would offer some support.

Not making a statement of "how things really are" here, just saying that sometimes an explanation might be "jeez, finally there's some change, maybe something will happen out of this" and not "let me go support these genocidal mercenaries".