In this Virgo Environment Traced in CO (VERTICO) science paper, we aim to study how the star formation process depends on the galactic environment and gravitational interactions in the context of galaxy evolution. We explore the scaling relation between the star formation rate surface density ({Sigma}_SFR_) and the molecular gas surface density ({Sigma}_mol_), also known as the Kennicutt-Schmidt relation, in a subsample of Virgo cluster spiral galaxies. We used new Atacama Compact Array and Total Power (ACA+TP) observations from the VERTICO-Atacama Large Millimeter/submillimeter Array (ALMA) Large Program at 720pc resolution to resolve the molecular gas content, as traced by the ^12^CO(2-1) transition, across the disks of 37 spiral galaxies in the Virgo cluster. In combination with archival UV and IR observations used to determine the star formation rate (SFR), we estimated the parameters of the Kennicutt-Schmidt (KS) relation for the entire ensemble of galaxies, and within individual galaxies. We find the KS slope for the entire population to be N=0.97+/-0.07, with a characteristic molecular gas depletion time of 1.86Gyr for our full sample, which is in agreement with previous work in isolated, nearby star-forming galaxies. In individual galaxies, we find that the KS slope ranges between 0.69 and 1.40, and that typical star formation efficiencies of molecular gas can vary from galaxy to galaxy by a factor of ~4. These galaxy-to-galaxy variations account for ~0.20dex in scatter in the ensemble KS relation, which is characterized by a 0.42dex scatter. In addition, we find that the HI-deficient galaxies in the Virgo cluster show a steeper resolved KS relation and lower molecular gas efficiencies than HI-normal cluster galaxies. While the molecular gas content in galaxies residing in the Virgo cluster appears - to first order - to behave similarly to that in isolated galaxies, our VERTICO sample of galaxies shows that cluster environments play a key role in regulating star formation. The environmental mechanisms affecting the HI galaxy content also have a direct impact on the star formation efficiency of molecular gas in cluster galaxies, leading to longer depletion times in HI-deficient members.