The answer in part is that not all the elements up through $\ce{Xe}$ have (or had until fairly recently) a nonrelativistic correlation consistent basis set. Specifically, the alkali and alkaline earth elements (columns 1 and 2 of the periodic table) have been much slower to get nonrelativistic basis sets. The cc-pVnZ basis sets for $\ce{Li}, \text{ }\ce{Be}, \text{ }\ce{Na}, \text{ and } \ce{Mg}$ were only published in 2011.[1] As you mentioned, $\ce{K}$ was very recent, but $\ce{Ca}$ only got cc-pVnZ basis sets in 2002.[2] Neither $\ce{Rb}$ nor $\ce{Sr}$ have a nonrelativistic cc-basis set. This discrepancy was mentioned in a recent article[3] that defined relativistic cc-basis for the alkali and alkaline earth metals, it was not further explained.
As to why these took so long, it may just have been a lack of interest in these atoms. Both the p-block and transition metal elements are widely studied in chemistry, but the alkali and alkaline earth metals have generally not been as studied (at least, not in contexts requiring insight from electronic structure theory). The previously discussed $\ce{Ca}$ basis was made specifically so they could better characterize the potential energy surface of a compound that had seen limited experimental or theoretical interest. So it doesn't seem to be due to any inherent difficulty in making basis sets for these atoms. Rather they seemed to just hold off until there enough potential applications to warrant it.
References:
[1] Prascher, B.P., Woon, D.E., Peterson, K.A. et al. Gaussian basis sets for use in correlated molecular calculations. VII. Valence, core-valence, and scalar relativistic basis sets for Li, Be, Na, and Mg. Theor Chem Acc 128, 69–82 (2011). DOI: 10.1007/s00214-010-0764-0
[2] Koput, J. & Peterson K.A. J. Phys. Chem. A 2002, 106, 41, 9595-9599 DOI:10.1021/jp026283u
[3] Hill, J.G. & Peterson K.A. Gaussian basis sets for use in correlated molecular calculations. XI. Pseudopotential-based and all-electron relativistic basis sets for alkali metal (K–Fr) and alkaline earth (Ca–Ra) elements
J. Chem. Phys. 147, 244106 (2017); DOI: 10.1063/1.5010587