How could a digital multiplexer transmit at a rate higher than its input?
Nothing magical about it. Perhaps you are getting confused because your diagram is just of the "selector" type multiplexer which is just a bunch of switches that connects the output to ONE of many inputs. With nothing but switches, what comes out is literally what comes in so of course the output must match an input somewhere.

But that's not the kind of multiplexer you are actually asking about. The kind of multiplexer you are asking about combines multiple data streams together so they can be transitted on the same medium and consists of processors and circuitry that can sample, encode, and re-transmit the signal. This is, perhaps more accurately, called an encoder. But there are encoders that do not multiplex multiple signals together.

If you have n-input channels each with a data rate of x, then you just have your multiplexing encoder simultaneously sample all channels at a rate of x, and for each round of samples it just encodes and blasts off the data down the line at a rate of n*x plus overhead.

The demultiplexing decoder does the opposite. It is receiving an encoded stream at a rate of n*x, and every time a full set of channel data is received it updates the outputs of the demux.