We report results from {\it XMM-Newton} observations of thirteen X-ray bright BL Lacertae objects, selected from the {\it Einstein} Slew Survey sample. The survey was designed to look for evidence of departures of the X-ray spectra from a simple power law shape (i.e., curvature and/or line features), and to find objects worthy of deeper study. Our data are generally well fit by power-law models, with three cases having hard ($\Gamma<2; dN/dE \propto E^{-\Gamma}$) spectra that indicate synchrotron peaks at $E \gsim 5$ keV. Previous data had suggested a presence of absorption features in the X-ray spectra of some BL Lacs. In contrast, none of these spectra show convincing examples of line features, either in absorption or emission, suggesting that such features are rare amongst BL Lacs, or, more likely, artifacts caused by instrumental effects. We find significant evidence for intrinsic curvature (steepening by $d\Gamma / d({\rm log} E) = 0.4 \pm 0.15$) in fourteen of the seventeen X-ray spectra. This cannot be explained satisfactorily via excess absorption, since the curvature is essentially constant from $0.5-6$ keV, an observation which is inconsistent with the modest amounts of absorption that would be required. We use the {\it XMM-Newton} Optical Monitor data with concurrent radio monitoring to derive broadband spectral energy distributions and peak frequency estimates. From these we examine models of synchrotron emission and model the spectral curvature we see as the result of episodic particle acceleration.