The mass of molecular gas and the star formation rate appear to be correlated across a wide range of scales from individual molecular clouds to entire galaxies. However, the star formation efficiencies derived differ by an order of magnitude between these different size regimes. I will present the results of our multiwavelength campaign in the nearby (1.9 Mpc) spiral galaxy NGC 300 in which we investigated the relationship between gas mass and star formation rate at 250 pc scales in a sample of 76 H II regions. We targeted these regions with APEX CO(2-1) observations in order to study their molecular gas content. To derive star formation rates, I have developed a new method that utilizes population synthesis modeling of individual regions and accounts for both the presence of extinction and the short (< 10 Myr) timescales appropriate for cloud-scale star formation. The NGC 300 sample smoothly extends the relation between total gas mass and star formation rate in Milky Way clouds by an order of magnitude. I will furthermore show that the average gas depletion time (the inverse of the efficiency) at cloud scales in NGC 300 is similar to that in the Milky Way clouds, and significantly shorter than depletion times measured over kpc-sized regions in nearby galaxies. I will conclude with results from a follow-up survey that spatially resolves molecular clouds in NGC 300 with the Submillimeter Array, revealing a population with similar properties to clouds in the Milky Way and other spiral galaxies.