The Complete Calibration of the Colour-Redshift Relation survey (C3R2) is a spectroscopic effort involving ESO and Keck facilities designed specifically to empirically calibrate the galaxy colour-redshift relation - P(zjC) to the Euclid depth (i_AB_=24.5) and is intimately linked to the success of upcoming Stage IV dark energy missions based on weak lensing cosmology. The aim is to build a spectroscopic calibration sample that is as representative as possible of the galaxies of the Euclid weak lensing sample. In order to minimise the number of spectroscopic observations necessary to fill the gaps in current knowledge of the P(zjC), self-organising map (SOM) representations of the galaxy colour space have been constructed. Here we present the first results of an ESO@VLT Large Programme approved in the context of C3R2, which makes use of the two VLT optical and near-infrared multi-object spectrographs, FORS2 and KMOS. This data release paper focuses on high-quality spectroscopic redshifts of high-redshift galaxies observed with the KMOS spectrograph in the near-infrared H- and K-bands. A total of 424 highly-reliable redshifts are measured in the 1.3<=z<=2.5 range, with total success rates of 60.7% in the H-band and 32.8% in the K-band. The newly determined redshifts fill 55% of high (mainly regions with no spectroscopic measurements) and 35% of lower (regions with low-resolution/low-quality spectroscopic measurements) priority empty SOMgrid cells.We measured H fluxes in a 1.2" radius aperture from the spectra of the spectroscopically confirmed galaxies and converted them into star formation rates. In addition, we performed an SED fitting analysis on the same sample in order to derive stellar masses, E(B-V), total magnitudes, and SFRs. We combine the results obtained from the spectra with those derived via SED fitting, and we show that the spectroscopic failures come from either weakly star-forming galaxies (at z<1.7, i.e. in the H-band) or low S/N spectra (in the K-band) of z>2 galaxies.