How efficiently can circuits over sets of naturals be transformed to boolean circuits?
A simple conversion process for $\boldsymbol\cup\,$, $\boldsymbol\cap\,$, constants, and complements

Note that any integer-set circuit representing a set $S \subseteq \{0,1,\ldots,N-1\}$ can be represented by a boolean circuit which tests $x \mathbin{\in?} S$ for $0 \leqslant x &lt; N$. If $N = 2^n$, this is a boolean circuit with $n$ inputs. We may construct such a circuit $C_n$ as follows.
$\def\GE#1{\mathrm{GE#1}}\def\PRIME={\mathrm{PRIME}}$


Using AND, OR, and NOT gates, we can very easily simulate equality of the input with a binary representation of any integer $0 \leqslant x &lt; 2^n$ with a circuit of size $n$ and depth $\log (n)$. 
Next, we may represent your input sets as also being constructed by $\cup$ circuits, constructed from singletons $\{x\}$ for $1 \leqslant x &lt; N$. If $S_j$ has size $m_j \leqslant M$, this requires a circuit with a boolean tree structure, with $m-1$ union gates, having depth at most $\log(m)$.  
Finally, we may represent unions and intersections of your sets $S_j$ by logical ANDs and ORs of membership in the input sets. This part of the circuit has the same size $s$ and depth $d$ as the depth of your integer-set-circuit.


We may then obtain a boolean circuit $C_n$ of depth at most $d + \log m + \log n$ and size at most $s + m + mn$. The complexity of building this circuit is essentially $O(s + m(\log m + n \log n))$, arising from doing the necessary construction of the binary trees for the gates representing each $S_j$ and $\{x\}$ for $x \in S_j$.

Note that the complexity does not increase at all if you allow logical complementation, which would represent in principle an infinitely large set including numbers larger than the input size; though to represent numbers which are $N$ or larger, we must use uniform circuit families $\{C_n\}$ rather than a single circuit $C_n$. The construction above will build these efficiently, however.

Remarks on the power of integer-set circuits with arithmetic

In the (extremely powerful!) model of arithmetic circuits including $+$ and $\times$ gates, this construction fails because the outputs to those gates implicitly involve existential quantifiers over satisfying inputs to subcircuits of arbitrary size. As your linked article notes, the Goldbach conjecture can be tested by evaluating $G(0)$, where $G$ is a (finite depth!) circuit,
$$ G :=\overline{\{0\} \times \Bigl(\bigl[ \{2\} \times \GE2 \bigr] \cap \bigl[\; \overline{\PRIME + \PRIME}\;\bigr]\Bigr)} \;, $$
where $\GE2 := \overline{\{0\} \cup \{1\}}$ tests whether an input is $\geqslant 2$, and $\PRIME := \GE2 \cap \bigl[\,\overline{\GE2 \times \GE2}\,\bigr]$ tests whether an input is prime. The enormous power of these circuits seem to me to come from combining negation (which allows you to obtain infinite sets from finite ones) with the $+$ and $\times$ gates (which allow existential quantification over all inputs to sub-circuits, as to whether there are accepted inputs whose sum or product is equal to the input integer). If you do not have additions or multiplications, those quantifications are absent, and the problem becomes much simpler &mdash; indeed, very close in flavour to a run-of-the-mill boolean circuit.