I'm looking for the earliest source that calls any rabbi "Kadosh", like calling R' Yehuda "Rabeynu Hakadosh", or "Rashi Hakadosh", or ZaTZuKa"L (זצוק"ל), etc.
The Gemara in Shabbos 118b writes about Rabbi Yehuda HaNasi:
אָמַר רַבִּי יוֹסֵי: מִיָּמַי לֹא נִסְתַּכַּלְתִּי בַּמִּילָּה שֶׁלִּי. אִינִי? וְהָאֲמַרוּ לֵיהּ לְרַבִּי: מַאי טַעְמָא קָרוּ לָךְ רַבֵּינוּ הַקָּדוֹשׁ? אֲמַר לְהוּ: מִיָּמַי לֹא נִסְתַּכַּלְתִּי בַּמִּילָּה שֶׁלִּי. בְּרַבִּי מִילְּתָא אַחֲרִיתִי הֲוָה בֵּיהּ, שֶׁלֹּא הִכְנִיס יָדוֹ תַּחַת אַבְנֵטוֹ. וְאָמַר רַבִּי יוֹסֵי: מִיָּמַי לֹא רָאוּ קוֹרוֹת בֵּיתִי אִימְרֵי חֲלוּקִי.
Rabbi Yosei said: In all my days, due to modesty, I never looked at my circumcision. The Gemara asks: Is that so? Didn’t they say to Rabbi Yehuda HaNasi: Why did they call you our holy Rabbi? He said to them: It is because in all my days I never looked at my circumcision. If so, why wasn’t Rabbi Yosei also called our holy Rabbi? The Gemara replies: In the case of Rabbi Yehuda HaNasi, another matter of modesty was present in him, as he did not insert his hand below his belt due to his great modesty. And Rabbi Yosei said: In all my days, the walls of my house never saw the seams of my robe due to modesty, as he would only undress under his bed sheets. (Sefaria translation and notation)
Also see Pesachim 37a:
אָמַר רַב יִרְמְיָה בַּר אַבָּא: שְׁאֵילִית אֶת רַבִּי בְּיִחוּד, וּמַנּוּ: רַב. אִיכָּא דְּאָמְרִי, רַב יִרְמְיָה בַּר אַבָּא אָמַר רַב: שְׁאֵילִית אֶת רַבִּי בְּיִחוּד, וּמַנּוּ: רַבֵּינוּ הַקָּדוֹשׁ. מַאי פַּת עָבָה? פַּת מְרוּבָּה. וְאַמַּאי קָרוּ לֵיהּ פַּת עָבָה? מִשּׁוּם דִּנְפִישָׁא בְּלִישָׁה. וְאִי בָּעֵית אֵימָא, בְּאַתְרֵיהּ דְּהַאי תַּנָּא לְפַת מְרוּבָּה — פַּת עָבָה קָרוּ לֵיהּ.
Rabbi Yirmeya bar Abba said: I asked my special Rabbi, and who is this? Rav. Some say that Rabbi Yirmeya bar Abba said that Rav said: I asked my special Rabbi, and who is this? Our holy Rabbi, Rabbi Yehuda HaNasi: What is the meaning of the expression: Pat ava? He explained that it means: A large quantity of bread, a large batch of dough prepared in one session. And why did they call it: Pat ava, thick bread? It is referred to by this name due to the fact that it requires a large amount of kneading. And if you wish, say instead that in the place where this tanna lived, a large quantity of bread was simply called pat ava, thick bread. (Sefaria translation & notation)