We use the 4Ms CDF-S survey to place direct X-ray constraints on the ubiquity of z~2 heavily obscured AGNs in K<22 BzK galaxies. Forty seven of the 222 BzK galaxies in the central region of the CDF-S are detected at X-ray energies, 11 of which have hard X-ray spectral slopes (Gamma<1) indicating the presence of heavily obscured AGN activity. The other 36 X-ray detected BzK galaxies appear to be relatively unobscured AGNs and starburst galaxies; we use X-ray variability analyses over a rest-frame baseline of ~3 years to further confirm the presence of AGN activity in many of these systems. The majority (7 out of 11) of the heavily obscured AGNs have excess IR emission over that expected from star formation (termed IR-excess galaxies). However, we find that X-ray detected heavily obscured AGNs only comprise ~25% of the IR-excess galaxy population, which is otherwise composed of relatively unobscured AGNs and starburst galaxies. We find that the typical X-ray spectrum of the heavily obscured AGNs is better characterized by a pure reflection model than an absorbed power-law model, suggesting extreme Compton-thick absorption in some systems. We verify this result by producing a composite rest-frame 2-20 keV spectrum, which has a similar shape as a reflection-dominated X-ray spectrum and reveals an emission feature at rest-frame energy ~6.4 keV, likely to be due to Fe K. These heavily obscured AGNs are likely to be the distant analogs of the reflection-dominated AGNs recently identified at z~0 with >10 keV observatories. On the basis of these analyses we estimate the space density for typical (intrinsic X-ray luminosities of L_X>1E43 erg/s) heavily obscured and Compton-thick AGNs at z~2. Our space-density constraints are conservative lower limits but they are already consistent with the range of predictions from X-ray background models.