Do dust storms only occur on planets with an atmosphere? And does their severity depend on how dense the atmosphere is?
"The planetary magnetosphere comes into play with the charged dust particles. The rotation of Saturn’s magnetic field generates an electric field directed radially outward from the planet. This field will eject small, electrically charged particles, into interplanetary space. Once that happens, the interplanetary magnetic field “frozen” into the solar wind can accelerate the dust particles to high speeds, creating the bursts of particles recorded by cosmic dust detectors. Evidence for this interpretation came from the changes in direction of the stream particles when the interplanetary magnetic field changed direction, in close timing with the Sun’s rotation."
So my guess is that a planet with no atmosphere and a magnetosphere weak enough to accelerate the charged dust just only enough to keep it moving without being ejected of the planet could have something happening, I'm not a planetary scientist and I don't know if a storm would be plausible so take it with a grain of salt and hope for someone else to jump on the question.
But if we're talking about "common" dust storms, without an atmosphere there would be no winds, so no common storms, and since air density in Mars is much lower than Earth (around 1% of ours), high speed storms in Mars would not be as severe as in Earth, wind speeds that would turn a car or rip trees on Earth wouldn't even push a human out of his place in Mars.