The surface of modern Mars is largely shaped by wind, but the influence of past wind activity is less well constrained. Sedimentary rocks exposed in the lower foothills of Aeolis Mons, the central mound within Gale crater, record a transition from predominantly lacustrine deposition in the Murray formation to aeolian deposition in the Mirador formation. Here, we report a series of enigmatic decameter-wide, concave-up scour-and-fill structures within the Mirador formation and discuss their formation mechanisms. Using panoramic images of stratigraphy exposed in cliff faces acquired by the Curiosity rover, we map the extent, distribution and orientation of the scour-and-fill structures and document the sedimentary facies within and surrounding these structures. The scours are grouped into two classes: (A) scours with a simple, symmetric morphology and light-toned, draping infill; and (B) scours with lateral pinching and dark-toned infill. We find that the scour-enclosing environment is composed of planar, even-in-thickness laminations with a pin-stripe pattern which we interpret as wind-ripple strata formed within an aeolian sandsheet environment. Class B contains cm-scale cross-bedding and a wing-shaped feature making this scour-and-fill structure consistent with fluvial processes. We interpret scour fill of class A as an aeolian infill due to similarities with the surrounding sandsheet strata. The broad morphologies and distribution of class A are also consistent with the geometry of blowout structures formed by localized, enhanced wind deflation. These paleo-blowout structures occur clustered within the same stratigraphic interval, which may imply that they record an interval of intensified wind activity at Gale crater.