It is a well established empirical fact that the surface density of the star formation rate, Sigma_SFR, strongly correlates with the surface density of molecular hydrogen, Sigma_H2, at least when averaged over large (~kpc) scales. Much less is known, however, if (and how) the Sigma_SFR-Sigma_H2 relation depends on environmental parameters, such as the metallicity or the UV radiation field in the interstellar medium (ISM). Furthermore, observations indicate that the scatter in the Sigma_SFR-Sigma_H2 relation increases rapidly with decreasing averaging scale. How the scale-dependent scatter is generated and how one recovers a tight ~ kpc scale Sigma_SFR-Sigma_H2 relation in the first place is still largely debated. Here, these questions are explored with hydrodynamical simulations that follow the formation and destruction of H2, include radiative transfer of UV radiation, and resolve the ISM on ~60 pc scales. We find that within the considered range of H2 surface densities (10-100 Msun/pc^2) the Sigma_SFR-Sigma_H2 relation is steeper in environments of low metallicity and/or high radiation fields (compared to the Galaxy), that the star formation rate at a given H2 surface density is larger, and the scatter is increased. Deviations from a universal Sigma_SFR-Sigma_H2 relation should be particularly relevant for high redshift galaxies or for low-metallicity dwarfs at z~0. We also find that the use of time-averaged SFRs produces a large, scale dependent scatter in the Sigma_SFR-Sigma_H2 relation. Given the plethora of observational data expected from upcoming surveys such as ALMA the scale-scatter relation may indeed become a valuable tool for determining the physical mechanisms connecting star formation and H2 formation.