We compare the structure of molecular gas at 40pc resolution to the ability of gas to form stars across the disk of the spiral galaxy M51. We break the PdBI Arcsecond Whirlpool Survey (PAWS; Schinnerer+ 2013ApJ...779...42S) into 370pc and 1.1kpc resolution elements, and within each we estimate the molecular gas depletion time ({tau}_Dep_^mol^), the star-formation efficiency per free-fall time ({epsilon}_ff_), and the mass-weighted cloud-scale (40pc) properties of the molecular gas: surface density, {Sigma}, line width, {sigma}, and b={Sigma}/{sigma}^2^{propto}{alpha}_vir_^-1^, a parameter that traces the boundedness of the gas. We show that the cloud-scale surface density appears to be a reasonable proxy for mean volume density. Applying this, we find a typical star-formation efficiency per free-fall time, {epsilon}_ff_(<{Sigma}_40pc_>)~0.3%-0.36%, lower than adopted in many models and found for local clouds. Furthermore, the efficiency per free-fall time anti-correlates with both {Sigma} and {sigma}, in some tension with turbulent star-formation models. The best predictor of the rate of star formation per unit gas mass in our analysis is b={Sigma}/{sigma}^2^, tracing the strength of self-gravity, with {tau}_Dep_^mol^{propto}b^-0.9^. The sense of the correlation is that gas with stronger self-gravity (higher b) forms stars at a higher rate (low {tau}_Dep_^mol^). The different regions of the galaxy mostly overlap in {tau}_Dep_^mol^ as a function of b, so that low b explains the surprisingly high {tau}_Dep_^mol^ found toward the inner spiral arms found by Meidt et al. (2013ApJ...779...45M).