Good gods: Completely fine. It is never a crime to worship a Good god, nor to be their cleric (or inquisitor or paladin or...). They are guessing he doesn't want information about ecclesiastical courts in Mendev.
Evil gods: Mendev is a Good country! They're not going to decide that actually Evil gods are totally fine! They have various straightforward treaty-compliant exceptions for Chelish detachments, the Order of the Godclaw, independent adventurers, etc., and the aforementioned procedures for non-independent adventurers, but that's completely different from just declaring it legal. In practice they enforce the law much more strictly for anything demon-adjacent (unempowered thieves who pray to Norgorber get sent to the Condemned, unempowered Baphomite thieves get the noose), and in practice they're only going to notice anyone unempowered if they're committing other crimes, but for clerics who didn't go through the procedure to get a dispensation it generally doesn't make a difference — you can't send a Norgorberite cleric to the Condemned, you'd be risking them channeling negative at a key moment in a battle.
Neutral gods: In practice, clerics of Neutral gods that channel positive are also completely allowed, even if their god is controversial. (Mendevian law does not consider the sort of entity that drives people mad with even the slightest touch to be relevantly 'gods,' though it's not like madmen are generally trying to join the army.) Negative-channeling clerics of Neutral gods are subject to much more intense scrutiny (in practice mainly amounting to carefully interviewing them to assess whether they're plotting sabotage, supervising their activities, and trying to give them as many opportunities to do Good as possible so they can be more militarily useful). This includes negative-channeling clerics of Lawful Neutral gods; the Second Crusade had a bad experience with a cult of the minor goddess Alseta that believed any attempt at closing the Worldwound to be blasphemous. ...Prior to the Worldwound opening there were technically some laws restricting some of the Neutral gods, but no one thinks of those as real laws anymore, he doesn't need to worry about them. There are currently a few faith-specific restrictions (for example, clerics of Groetus are forbidden from preaching regardless of how they channel), and they've accumulated some wisdom about tasks that it's unwise to assign clerics of specific gods to, but they're really much less worried about him enforcing any of that than about him deciding he considers any of their positive-channeling clerics objectionable.
(His officers know somewhat more about how things are done in Lastwall than the common soldiers, but some of them are definitely still misinformed. One of them is apparently under the impression Lastwall bans clerics of every Chaotic god but Desna. One of them thinks Lastwall executes prostitutes working in the cities, though not camp followers, and also anyone who ever prays to Calistria. More than one of them believes that the Order of the Godclaw has been blessed by Iomedae and counts Lastfolk among its founding members.)
Witchcraft is handled separately, and subject to its own restrictions, though if they're understanding right it sounds like that's also the case in Lastwall. It doesn't come up much, witches are mostly Evildoers serving the demons and uninterested in restraining themselves enough to infiltrate the army.