「彼らは政治的な発言をすべきではなかったかもしれない」って英語でなんて言うの？

Maybeを文頭において、should have not doneを用います。 またはI think they should not have done.とすると、質問者様のニュアンスは出せます。

Should not have の前にprobablyをつけてあげれば「おそらく」という意味合いを足してあげることが出来るので、それが一番シンプルで簡単なやり方かと思います。 参考にしてください

should have done を使えば might とは共存できませんが、 「すべきではなかった」 に違う動詞を使うという手もあります。 つまり、「〜することを避ければよかった」とすれば 　might have been better to avoid 〜ing とできます。 今回の場合なら、続きは making political statements となるので、 　They might have been better to avoid making political statements. を回答としました。