We investigate the dynamics of kinetically frozen block copolymer micelles of different softness across a wide range of particle concentrations, from the fluid to the onset of glassy behavior, through a combination of rheology, dynamic light scattering, and pulsed field gradient NMR spectroscopy. We additionally perform Brownian dynamics simulations based on an ultrasoft coarse-grained potential, which are found to be in quantitative agreement with experiments, capturing even the very details of dynamic structure factors $S(Q,t)$ on approaching the glass transition. We provide evidence that for these systems the Stokes-Einstein relation holds up to the glass transition; given that it is violated for dense suspensions of hard colloids, our findings suggest that its validity is an intriguing signature of ultrasoft interactions.