Two dimmers controlling LED strips and blinkig at certain levels
My idea is that the dimmers, being PWMs, consume power in impulses.

Yes

I suspect that the frequency of the PWM varies slightly with power.

Unlikely. They're microcontrollers, their clock either comes from a quartz or a RC oscillator on the chip which would depend on power supply voltage but there's a 3V3 or 5V regulator in there so it should be stable.
But even if the frequencies don't change, your two dimmers will have slightly different frequency due to component tolerance, so your original idea still holds:

So two PWMs with slightly different frequencies can produce a wobble frequency in power consumption which the power supply fails to compensate.

Yes, and that's probably the cause. It shouldn't happen since the power supply is rated for &quot;10A&quot; and your LED strips draw 7A when fully on, but that depends on the quality of the power supply... if it's cheap, who knows.
option 2 in your answer: Do not put capacitors in parallel with the LED strips: a cap after the PWM switch would draw large pulsed current every time the PWM switch turns on.
option 1 in your answer: Yes you should try putting a large cap just at the output of the power supply. It should be low-ESR, which means either a high value general purpose cap like 4700µF or more, or a special low-ESR cap.