I have been taught that the first stars to be "born" could not use the CNO cycle to fuse Hydrogen into Helium as there were no elements heavier than Helium and a bit of Lithium to use in those reactions. Since high-mass stars fuse H to He using the CNO cycle, does that mean that the first stars were low-mass stars and had to fuse H to He using the proton-proton chain? In addition, is the fusion of He to C in the core of these first stars, followed by their explosions how Carbon was first introduced to the interstellar medium?
It is likely that the first stars were more massive than most born today. You are correct though, that as they would have no heavy elements, they must have fused hydrogen via the pp chain.
You misunderstand the competition between the pp chain and CNO cycle. The latter has a much stronger temperature dependence, so if these heavier nuclei exist in the core of a star, then the CNO cycle dominates at the higher temperatures inside higher mass stars.
That does not mean the pp chain cannot occur. In the first stars the central temperatures would just need to be that little bit hotter to compensate for the slower pp chain.
The first carbon would have been made in the helium-burning cores of the first massive stars. This is then disseminated to the interstellar medium by supernovae.