We present the results of a galaxy-wide study of molecular gas and star formation in a sample of 76 H II regions in the nearby spiral galaxy NGC 300. We have measured the molecular gas at 250pc scales using pointed CO(J=2-1) observations with the Atacama Pathfinder Experiment telescope. We detect CO in 42 of our targets, deriving molecular gas masses ranging from our sensitivity limit of ~10^5^M_{sun}_ to 7x10^5^M_{sun}_. We find a clear decline in the CO detection rate with galactocentric distance, which we attribute primarily to the decreasing radial metallicity gradient in NGC 300. We combine Galaxy Evolution Explorer far-ultraviolet, Spitzer 24{mu}m, and H{alpha} narrowband imaging to measure the star formation activity in our sample. We have developed a new direct modeling approach for computing star formation rates (SFRs) that utilizes these data and population synthesis models to derive the masses and ages of the young stellar clusters associated with each of our H II region targets. We find a characteristic gas depletion time of 230Myr at 250pc scales in NGC 300, more similar to the results obtained for Milky Way giant molecular clouds than the longer (>2Gyr) global depletion times derived for entire galaxies and kiloparsec-sized regions within them. This difference is partially due to the fact that our study accounts for only the gas and stars within the youngest star-forming regions. We also note a large scatter in the NGC 300 SFR-molecular gas mass scaling relation that is furthermore consistent with the Milky Way cloud results. This scatter likely represents real differences in giant molecular cloud physical properties such as the dense gas fraction.