We compare the structure of molecular gas at 40 pc resolution to the ability of gas to form stars across the disk of the spiral galaxy M51. We break the PAWS survey into 370 pc and 1.1 kpc resolution elements, and within each we estimate the molecular gas depletion time (tau(mol)(Dep)), the star-formation efficiency per free-fall time (epsilon(ff)), and the mass-weighted cloud-scale (40 pc) properties of the molecular gas: surface density, Sigma, line width, sigma, and b equivalent to Sigma/sigma(2) proportional to alpha(-1)(vir), 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(40) (pc)>) similar to 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 equivalent to Sigma/sigma(2), tracing the strength of self-gravity, with tau(mol)(Dep) proportional to 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(mol)(Dep)). The different regions of the galaxy mostly overlap in tau(mol)(Dep) as a function of b, so that low b explains the surprisingly high tau(mol)(Dep) found toward the inner spiral arms found by Meidt et al. (2013).