You are right, the differential stage has a single ended output that does change somewhat with common mode input changes. However this component is so small compared to the output's response to input difference, that we mostly don't care about it. It's not obvious why, so let me explain.
Total common mode rejection implies that as long as the inputs have the same potential, the output remains unchanged, and as both inputs rise or fall equally, that output stays rock solid at some value.
You might expect that value to be zero, since the typical control systems book will explain that the input-to-output relationship of an opamp is something like:
$$V_{OUT} = A \times (V_{NINV} - V_{INV})$$
Here \$A\$ is the opamp's open loop gain, of course. To be more complete, That equation should really include offsets at the input and output, that reflect some deviation from the ideal:
$$V_{OUT} = A \times (V_{NINV} - V_{INV} + V_{IN\_OFS}) + V_{OUT\_OFS}$$
In that right hand expression, as \$A\$ goes towards infinity, \$V_{OUT\_OFS}\$ becomes negligible compared to \$A(V_{NINV} - V_{INV} + V_{IN\_OFS})\$. It remains small, dwarfed by the huge value of the differential component multiplied by \$A\$.
By contrast, the value of \$V_{IN\_OFS}\$ still gets amplified by factor \$A\$, always being a significant component of the output, meaning that input offset is a big deal when building circuits with opamps.
The effects and consequences of input offset voltage is always well covered in the books, precisely because of its significant effect on the output voltage. Output offset voltage, on the other hand is frequently overlooked, simply because its influence is tiny compared to everything else.
Consider that any common mode component that makes it through to the output is what I refer to by the term \$V_{OUT\_OFS}\$. As I said, it is going to be tiny compared to the heavily amplified differential part. As long as gain \$A\$ is huge compared to whatever gain is applied to the common mode component, the real behaviour of the opamp will be very close to that of an ideal device:
$$
\text{for A >> B} \\
A \times (V_{NINV} - V_{INV}) + B \times V_{OUT\_OFS} \approx A \times (V_{NINV} - V_{INV})
$$
This is why you don't really need to completely reject the common mode component of the inputs to a differential pair. To put this idea into some context, consider the voltage follower, a non-inverting amplifier and an inverting one:
simulate this circuit – Schematic created using CircuitLab
Algebraically, all of these configurations make use of the opamp gain expression in their analyses, but with some qualitative analysis, we will be able to see intuitively how any output offset, introduced anywhere in the system, may be ignored. These systems all rely on negative feedback, where we feed some fraction of the output (X) back to the inverting input (Q).
Any rise in output X, causes a rise at inverting input Q. If X is not exactly the right value to make P and Q equal, X will change, as per the gain expression, in a direction that will reduce the difference between P and Q. If P is greater than Q, X will rise until Q becomes equal to P, and vice versa.
In other words, negative feedback causes output X to slew in the direction necessary to equalise inputs P and Q. If it over shoots that mark, the difference between P and Q changes sign, and the opamp reverses the direction of change of its output, always eventually settling at the state where P = Q. This all happens pretty much instantly.
Notice that at no point do we care what the current value of X is, because the opamp will always adjust it towards that point of equilibrium where P = Q. It doesn't matter if there's some offset present at X, the opamp's high gain will cause X to change in such a way that minimises the difference between P and Q, effectively compensating for that offset, rendering it moot.
This brings me back to your question about the differential stage failing to reject the common mode component of its inputs, and feeding that component through to its single-ended output. You are not wrong. That can and does indeed happen. In fact, that common mode component may even be amplified somewhat by subsequent stages, and appear at the output of the entire opamp, but it doesn't matter. The effect it has on shifting the output up or down is so small compared to the huge shifts that result from the tiniest difference in input potentials, that it is negligible in all but the most demanding applications.