Before suspecting the CNC machine, I’d double check that the table it sits on is itself flat and warp-free. Any distortion in the underlying table will telegraph through to the machine.
Your hunch sounds correct - if all four legs are not level, you can get a cup in one diagonal and a hump in the other. This can happen due to building movement (we live in California where we deal with both seasonal and earthquake movement!) , floor irregularities, etc… One fix is to shim up the two “low” legs and let the table readjust over a day or so.
A laser level and a 123 block you can move around the table top is an easy way to check without dismantling everything to fit a steel rule 