How can a neural network approximate all functions when the weights are not allowed to grow exponentially?
What is Proven
The question references the proof of Approximation by Superpositions of a Sigmoidal Function, G. Cybenko, 1989, Mathematics of Control, Signals, and Systems.
The 1989 proof stated that the network, made of activations that were required to be, &quot;Of continuous sigmoidal non-linearity,&quot; could, &quot;Uniformly approximate any continuous function of n real variables,&quot; so, as the question stated, the proof doesn't directly apply to 1-bit discrete outputs.  Note that the network is expected to merely approximate the desired circuit behavior.
The question defines the system as an arbitrary mapping from input bit vector

$I: { i_1, \; \dots, \; i_n}$

to output bit vector

$O: { o_1, \; \dots, \; o_n}$

It was further back proven that such a mapping can be accomplished with one Boolean expressions for each output bit.  For all $2^n$ possible input vector permutations, there exists a Boolean expression made up of AND and NOT operations that calculates a result that matches any arbitrary logical truth table.
There are techniques for reducing redundancy in the array of Boolean expressions, which is critical to VLSI chip layout.
Without the retention of state anywhere in the network other than the attenuation matrix (parameters), the system is not Turing complete.  However, with regard to the ability to realize Boolean expressions in describing the mapping, given an arbitrary number of layers, the network is complete.
Estimating Layer Depth Requirements
Only one inner layer is required in the 1989 proof, so how many layers would it take for an accurate n-bit-to-n-bit mapping to be learned?
The question proposes that there are $2^n$ to the power of $2^n$ permutations.  The mapping of each input bit vector to the desired output bit state can be represented by a truth table of $n$ binary dimensions.
Each output is an independent bit, meaning the $2^n$-bit representations of unique Boolean functions that could produce each output bit is not tied to any other output channel.  As would be expected, there are $2n$ freedoms of motion for the mapping of I to O.
For the case where the input is a bit vector of $n$ bits, where $n$ is the number of activations for any one of $L$ layers, the total number of activations in the network $a_t$ and the total number of scalar elements for all attenuation matrices (the parameters that represent training state) $q_t$ for the network is as follows.

$a_t = \sum_{\, 0 = v}^{L - 1} \; n_v$


$= n \, L$


$p_t = \sum_{\, 0 = v}^{L - 2} \; n_v^2$


$= n^2 \, (L-1)$



If IEEE 64 bit floating point numbers are used for each element in the attenuation matrix, we can calculate the number of bits available in the training parametrization.

$b_t = 64 \, (L - 1) \, n^2$

It would be normal today to use ReLU, leaky ReLU, or some other more quickly convergent activation instead of sigmoid for all layers but the last and use a simple binary threshold for the last.
Thus we have a formulation of the information theory comparison inferred by the question, and can reduce it.

$2^{2n} \le 64 \, (L - 1) \, n^2$
$L \ge 1 + \frac {2^{2n-6}} {n^2}$

This is a rough threshold.  For a highly reliable training for the binary inputs to binary outputs, the number of layers should be well above the threshold.
Below the threshold the trainability of the mapping will degrade to an inadequate approximation for most applications because of signal saturation in the back propagation mechanism.