Surface plasmons offer a promising avenue in the pursuit of swift and localized manipulation of magnetism for advanced magnetic storage and information processing technology. However, observing and understanding spatiotemporal interactions between surface plasmons and spins remains challenging, hindering optimal optical control of magnetism. Here, we demonstrate the spatiotemporal observation of patterned ultrafast demagnetization dynamics in permalloy mediated by propagating surface plasmon polaritons with sub-picosecond time- and sub-μm spatial- scales by employing Lorentz ultrafast electron microscopy combined with excitation through transient optical gratings. We discover correlated spatial distributions of demagnetization amplitude and surface plasmon polariton intensity, the latter characterized by photo-induced near-field electron microscopy. Furthermore, by comparing the results with patterned ultrafast demagnetization dynamics without surface plasmon polariton interaction, we show that the demagnetization is not only enhanced but also exhibits a spatiotemporal modulation near a spatial discontinuity (plasmonic hot spot). Our findings shed light on the intricate interplay between surface plasmons and spins, offer insights into the optimized control of optical excitation of magnetic materials and push the boundaries of ultrafast manipulation of magnetism.