What is the meaning of the first half of the Pasuk?
Rashi: Water will flow from their springs - A king will arise from their ranks who will rule over many nations. 1
Targum Yonasan: Their kings and their redeemers will come from their own ranks, and their children, the sons of Ya'akov will rule over many nations.
Rashi: He will succeed - like a seed that is planted in water. See also Ba'al ha'Turim, who comments that one only anoints a king by a river.
To whom does "Malko" refer?
Rashi, Ramban, Rashbam and Targum Yonasan: It refers to Shaul ha'Melech - their first king, who will capture Agag, king of Amalek.
How could Bil'am name the king of Amalek before he was borm?
Ramban #1 (citing Rashi): Bil'am is pre-naming Agag before he was born. 1
Ramban #2 and Rashbam: All kings of Amalek were called Agag. 2
Ramban (Ibid.): Just as we find by Koresh, king of Persia - in Yeshayah (45:1), by Yoshiyahu, king of Yehudah - in Melachim 1, 13:2, by Yitzchak and Yishmael - in Bereishis 17:19 & 16:11, respectively and by Sh'lomoh ha'Melech - in Divrei ha'Yamim 1, 22:9. See Ramban, as to why he opts for his second explanation.
Rashbam: Just as all the kings of Egypt were called Par'oh; all the kings of P'lishtim, Avimelech and all the kings of Yerushalayim, Malki Tzedek.
And what is the meaning of "Vesinasei Malchuso"?
Rashi and Ramban,: It means that they will go from strength to strength, because David and Shlomoh will follow.
Targum Yonasan: And because he (Shaul) had compassion on him (Agag), his kingdom was taken away from him.