We present deep near-infrared
$K_\textrm{s}$-band imaging for 35 of the 53 sources from the high-redshift (
$z \gt 2$) radio galaxy candidate sample defined in Broderick et al. (2022, PASA, 39, e061). These images were obtained using the High-Acuity Widefield K-band Imager (HAWK-I) on the Very Large Telescope. Host galaxies are detected for 27 of the sources, with
$K_\textrm{s} \approx 21.6$–23.0 mag (2
$^{\prime\prime}$ diameter apertures; AB). The remaining eight targets are not detected to a median
$3\unicode{x03C3}$ depth of
$K_\textrm{s} \approx 23.3$ mag (2
$^{\prime\prime}$ diameter apertures). We examine the radio and near-infrared flux densities of the 35 sources, comparing them to the known
$z \gt 3$ powerful radio galaxies with 500-MHz radio luminosities
$L_{500\,\textrm{MHz}} \gt 10^{27}$ W Hz
$^{-1}$. By plotting 150-MHz flux density versus
$K_\textrm{s}$-band flux density, we find that, similar to the sources from the literature, these new targets have large radio to near-infrared flux density ratios, but extending the distribution to fainter flux densities. Five of the eight HAWK-I deep non-detections have a median
$3\unicode{x03C3}$ lower limit of
$K_\textrm{s} \gtrsim 23.8$ mag (1
$.\!^{\prime\prime}$5 diameter apertures); these five targets, along with a further source from Broderick et al. (2022, PASA, 39, e061) with a deep non-detection (
$K_\textrm{s} \gtrsim 23.7$ mag;
$3\unicode{x03C3}$; 2
$^{\prime\prime}$ diameter aperture) in the Southern H-ATLAS Regions
$K_\textrm{s}$-band Survey, are considered candidates to be ultra-high-redshift (
$z \gt 5$) radio galaxies. The extreme radio to near-infrared flux density ratios (
$\gt 10^5$) for these six sources are comparable to TN J0924
$-$2201, GLEAM J0856
$+$0223 and TGSS J1530
$+$1049, the three known powerful radio galaxies at
$z \gt 5$. For a selection of galaxy templates with different stellar masses, we show that
$z \gtrsim 4.2$ is a plausible scenario for our ultra-high-redshift candidates if the stellar mass
$M_\textrm{*} \gtrsim 10^{10.5}$ M
$_\odot$. In general, the 35 targets studied have properties consistent with the previously known class of infrared-faint radio sources. We also discuss the prospects for finding more UHzRG candidates from wide and deep near-infrared surveys.