The Rashi (to Bamidbar 22:4) that you quote writes:
בעת ההוא. לֹא הָיָה רָאוּי לְמַלְכוּת, מִנְּסִיכֵי מִדְיָן הָיָה, וְכֵיוָן שֶׁמֵּת סִיחוֹן מִנּוּהוּ עֲלֵיהֶם לְצֹרֶךְ שָׁעָה :
At That Time — [Balak] that time: he was not really entitled to the kingdom; he was actually one of the Midianite princes, but when Sihon died they (the Moabites) appointed him as king over them to meet the needs of the time (Midrash Tanchuma, Balak 4).
We can deduce from here that while technically Balak was from Midian (ie a Midianite prince), when he was appointed Moabite king he was now considered to be a Moabite.