I think I see the issue here:
The apparent paradox is not that more information can be transmitted at once with denser coding, but that less information can be received from the signal, when transmitted through a given code.
Consider the digital signal not as a bitstream, but an analog signal summed with quantization noise. When we choose a bit depth, or constellation or whatever, we are adding an LSB's noise onto the signal at the outset!
Note that this works perfectly well all the way down to 1 bit (e.g. PWM, sigma-delta modulation). Often, a simple analog filter (or digital equivalent) suffices to recover such a signal; quantization noise is either small relative to the signal bandwidth by way of a large symbol rate to signal bandwidth ratio (i.e. Fclk >> BW), or confining the quantization noise to high frequencies ("noise shaping").
If we grow the number of symbols, we reduce quantization noise, and can trade that for bandwidth; but we still have the same underlying signal, and we cannot sample that signal lower than Nyquist, regardless of method.
If we are required to convey a signal of given bandwidth and SNR, we would've failed manifestly with an overly-coarse digital method (unless it's clocked fast enough to filter down in turn, in which case the bandwidth spreading is considerable); or using large enough symbol sets, to basically mimic the analog signal as-is (which, if we consider a discrete-time sampled and voltage-quantized signal, is just PCM coding).
The key factor is that: when we transmit an analog signal, we transmit it at as high fidelity as possible (or practical), subject it to additive (channel) noise, and receive whatever is left. SNR is a property of transmitter power versus channel background level. When we transmit a digital signal, we transmit it with quantization noise already added to it, hopefully at a level just above the channel SNR so that we recover the bits with satisfactory error rate without squandering channel capacity. We are necessarily using more bandwidth in the process (Fs strictly greater than Fnyquist), and how much extra is a free variable (we can always sample faster, or clock the S-D converter faster, but never slower).
So you say, what if we take multiple successive samples, cram them together, and transmit one uber-symbol at a time? What if we take two samples? Or 16? Or 256?
Well, let's be careful here, because we assumed the analog system is subject to channel noise, and so too the digital system ought to be. If we take even a modest number of samples together, concatenate bits (or interleave or whatever) and cram that through a DAC, we now get an analog signal that is exponentially more precise than we started with, and, frankly, we'll very quickly run into fundamental limitations of the physical world itself if we try this with more than a few samples.
Consider that just three samples at 16 bits each, already vastly exceeds the accuracy of the best known physical constant (Rydberg constant is known to 2 parts per trillion, or ~39 bits). You're welcome to cram as many bits in theory as you like, but give me a call when you pull it off in practice!
So why do we use digital modulations with such flexibility? Because the channel itself varies over time, in a lot of applications. Cell phones and laptops move around in an RF field, getting different SNRs on different channels in their respective radio bands. Likewise, the data rates themselves are extremely variable -- and flexible, for the most part. We might grumble a bit when a page loads less than instantaneously, but it ultimately doesn't matter; but good luck holding any kind of conversation when your voice channel drops below a few kbps.
And, voice drops might manifest as a broad range of errors. This is an illustration of channel capacity and error rate. Modern codecs attempt to approximate the human vocal tract, so that slowly changing vowels, or some consonants, can be transmitted at impressively low rates (or, low compared to the complexity of turbulent fricatives and the like); but so too, when they glitch out, you get some strange stuttering, staring-off-into-the-distance mouth-gaping "Aaaaaaəəəee" sound, for example; or more traditional channels might suffer clipping or distortion (PCM bit errors, say), or popping or dropouts (packet loss, time division multiplex errors). So too, analog voice systems have exhibited similar faults; the previous analog telephone system used a sophisticated set of frequency and time division multiplexers to squeeze more voice channels onto trunk lines, and modulation errors, crosstalk and dropouts were among the possible defects.
So for bandwidth, I think it works much easier one way than the other. That is, you can always spread bandwidth, but you'll have a hard time ever reducing it. Notice this is mirrored by the digital case, you can always sample or modulate faster, or spread spectrum or code sequence or whatever, but you can't sample slower. Conversely, you might transmit symbols slower, but the bit rate is the same, given much higher channel SNR to support it.
Bandwidth spreading has the advantage that, it's more tolerant of poor SNR -- if the spectral noise floor is higher, but you're folding a larger swath of it into a tinier signal based on certain correlations in that spectrum, well, that works just like filtering the S-D bitstream does; doesn't matter if we do it in frequency or time domain, or any weird nonlinear mixture. Consider wideband FM for example: the bandwidth spreading is significant, but it's also renowned for its clarity of reception.
As for proof by example -- this seems the trickiest so I'll add it here.
We can indeed accomplish bandwidth compression in the analog domain.
Suppose we have a 16 ENOB channel, and wish to transmit an 8 ENOB signal of given bandwidth. If we can fold the signal "in half" somehow, we can utilize the excess SNR and reduce bandwidth (and, I guess let's say the channel only has BW/2 available for some reason).
First, filter the signal into upper (UFB) and lower frequency (LFB) bands, using a "brick wall" filter (and its complement). Of the LFB, quantize it: this chops it into 256 discrete levels (8 bits). This isn't "unfair" in any way: it's just a nonlinear transfer function, and it's not even a discrete-time function (but those are fair game, too!).
Of the upper band, treat it as a USB signal: mix it with Fc = BW/2 to shift it down to baseband. Attenuate it by 256x and sum with the quantized low band. Congrats, you now have an analog solution with half the bandwidth!
Notice some nonlinear function is required here, because if we have continuous signals \$x(t)\$ and \$y(t)\$, their sum \$x(t) + y(t)\$ is also a continuous function indistinguishable from them. We need to introduce some method of identifying one and separating it from the other. Since our channel has low noise, discretizing the voltage (making one a discontinuous function) seems an option.
Note that this is a toy example, as it makes no effort to address channel bandwidth (causing inter-symbol interference, i.e. the low-pass signal varies smoothly over time, not in satisfyingly hard steps), nor mixing (the UFB levels add with ISI and noise to fudge what are supposed to the LFB's discrete steps), nor reasonable noise statistics (it would be passable at best for evenly distributed noise -- not normal distribution!). But an example is sufficient for existence; it doesn't have to be a working prototype.
Any function that allows discriminating two signals (that need not be continuous), from one continuous starting function, will do here. I'm not real sure offhand what all kinds of things would fit here. But that seems one way.
Notice that QAM does not help us here:
Suppose we do the same band splitting trick, getting us two continuous signals of BW/2 each. If we SSB each one, we get BW/2 each, again. If we superimpose them, well, er, we just get plain old SSB again -- that is if both are USB modulated, and the UFB is placed at a center frequency exactly its offset above the LFB. We just made a lot of steps for no value, heh. Note we can't superimpose them with overlap, because there's no phase information to separate them with. And if there were, well..:
Suppose we DSB modulate each signal. Individually, we've doubled the bandwidth (we have LSB+USB of the LFB, and LSB+USB of the UFB). AM doesn't seem to have any advantage for us, and SSB is the most efficient such method for a single signal. Well, suppose these DSBs are placed at the same center frequency, with one carrier 90° phase shifted: now we can superimpose them, and the sidebands carry the sum and difference of the two signals; they are separable by orthogonality. We can demodulate them using the reverse process, and recover the original signal; and, notice we've used a total 2 * (BW/2) bandwidth in the process. Well, on one hand, it would sound weird to an AM radio -- without a coherent quadrature detector, the sidebands overlap, and it might not be intelligible. Could be interesting effects there, but, quirks aside, there isn't anything to be gained here, not from such simple transformations at least.
And, these arguments remain true no matter how we slice up the signal. Suppose we write the signal alternately to two tapes: while a given record head is active, its tape advances at normal speed, and freezes on the spot otherwise. Both tapes, after a short loop (there has to be a little slack in the system, of course), are read out, continuously, at half speed: we again have two signals of half bandwidth (give or take the discontinuity as they are switched). We've doppler-shifted and time division multiplexed them. But, we're stuck with two signals.
