Забавный вариант. Но маги умные всё-таки...
Конкретно с церковью ничего не получится из-за специфики сеттинга. Была б она в городе вообще, то стала бы главным противником интригана. Можно правда возродить какие-нибудь древние языческие культы, но на это время нужно. В принципе, на место действующей организации можно было бы что-то другое поставить, вроде гильдии купцов или ещё чего. Основная проблема в том, что маги очень плотно в город вписались и занимают в нем очень уважаемое положение. Изменение общественного мнения будет делом сложным, учитывая большое число влиятельных граждан понимающих значение магов. Но стоит над этим подумать, может что и выйдет...
Все-таки убийцы, по-моему, оптимальный вариант. Для убийцы магов важно что? Пережить первый магический удар подобраться и... средний маг в большинстве случаев мертв.
Для убийцы магов нужно убить мага до того, как он сможет хоть что-то сделать... Ибо save-or-die спеллов на любом уровне заклинаний достаточно...
Король объясни, пожалуйста, подробнее что за город и какие земли его окружают.