We have a lot of potential clients which are tied to sets of ideals
(local branches of churches, political parties, the armed forces etc.)
What is an appropriate response to the situation?
I think you need to at least sit with the employee to discuss the objection in more detail. Does he know enough about this particular person to specifically say they "cheat people" and "scam the poor and gullible"? That is to say, does your employee believe this practitioner to be especially dishonest? Or does he mean that anyone who claims Tarot cards work is a "cheat" and a "scammer", as opposed to merely being wrong? Just because I don't think something works, doesn't mean that I should characterise those who genuinely try to make it work, as scammers. Making that generalisation goes rather further than merely not wishing to aid a suspected criminal. I'm not saying your employee is reflexively making an unfair judgement, but I do think a conscientious objector should be prepared to state their grounds.
If this is about characterising a belief as a lie, then you have a serious potential problem here with employees declaring that if he's allowed to act on the view that all fortune-tellers are liars and keep his job, then they should be allowed to act on the view that all Democrats (or all Republicans) are liars, and keep their job. Or that all members of the armed forces are cheats and scammers. Or that anyone who hasn't served is a cheat and a scammer. Or declare that vaccination isn't effective and therefore doctors are scammers. Whatever. One does not generally put one's clients to proof, especially when their claims are vague (as fortune-tellers' claims often are) or subjective.
Religion specifically might be a protected class for discrimination in your jurisdiction and if so then employees would know (or can be told) that you cannot legally refuse to supply services on the basis that "Christianity isn't true and therefore Christians are conning the gullible" or whatever a non-Christian might think. But that only deals with protected classes, not with all the clients who might be rejected due to their principles.
I consider all these generalisations bizarre (including the one about all Tarot card readers being cheats), so as far as I can see once you allow one characterisation of a belief as a lie, you open the door to a lot of them. But if the employee does have specific concerns about what this particular potential client is doing, then accommodating those concerns need not open the door to employees declaring anyone who disagrees with them to be a fraud! But you have to be clear with yourself about what grounds you're accepting if you want to be consistent in future.
Therefore, do not allow the objection on grounds that all fortune-tellers are frauds, but admit the possibility of objecting on grounds that this one is abusive. Encourage the employee either to express to you his specific concerns about the honesty of this person (perhaps even to the point of convincing you that quite aside from their religious or magical beliefs, they're a crook), or else to accept that as a commercial business you aren't going to refuse every client whose business revolves around an opinion or belief that you consider absurd, and that he shouldn't either.
The result of this might be that the employee restates his objection -- not that this person is dishonest, but that regardless of honesty or dishonesty, fortune-telling is unethical and they feel they cannot work for a fortune-teller. At least then you have a new question, "should I allow employees to decline to work for clients on grounds that the client's beliefs differ from their own", and you can think about when that would be appropriate without the waters being muddied by a claim of dishonesty that might not be accurate.
Ultimately, as someone else has said, you might have to treat this pragmatically. Whether you consider the refusal reasonable or not, if he continues to refuse the task then you can either accommodate this or else sack him. The low-risk option seems to be to accommodate it. If such requests start to get out of hand (because your employees start to develop more and more conflicting views of which clients to take, or because they become so picky that business is constrained well past what you want) then you can always change your policy later, again as a pragmatic matter, on the grounds that the cost to the business has been much higher than anticipated.
There are some companies that only take on clients they're aligned with religiously/politically/whatever, but it's not the norm and employees won't generally expect it. So I think the risk of it getting out of hand is probably low.