I think they were wrong in firing him -- grounds of religion, race, color, etc.
There are clearly carved-out exceptions to that, Salvation. Your parish is free to hire Catholics only. A Presbyterian church is free to hire only Presbyterians. Any other outcome would be absurd.