The nonlinear propagation of low-frequency circularly polarized waves in a magnetized dusty plasma is analyzed. It is found that wave steepening and shock formation can take place due to the presence of nonlinear quantum vacuum effects, thus giving rise to ultra-intense electromagnetic shocks. Moreover, it is shown that solitary wave structures are admitted even under moderate astrophysical conditions. The results may have applications to astrophysical plasmas, as well as next generation laser interactions with laboratory plasmas containing dust clusters.