Because I am currently too tired to do an exhaustive search on all the sources in the Shulhan Arukh, I am basing my answer on Mori HaRav Neuwirth and his sefer Shemirat Shabbat K'Hilkhata.
According to the above sefer 10:1 there is no issue of Nolad when melting ice, even if the the water goes to waste, if it is used to cool other foods that are normally consumed cold(ice-cream would count).
As far as freezing milk 10:5b, specifically says that you can. He states in 10:6 that one may not make ice-cream from a powder, however he goes on to state in 10:7 that as long as the liquid has been prepared in a manner that is permissible, see chapter 6, then one may make ice-cream from that.
That would typically sum up the Israeli Ashkenazi Hareidi opinion. Rav Ovadia Yosef, to my poor remembrance does not rule contrary, though that would not necessarily mean that is permissible for all Sephardim, as there are other legal codes to be considered that I have not checked.
Further Rav Moshe Feinstein often disagrees with R' Neuwrith(actually he disagrees with R' S.Z. Auerbach whose ruling R' Neuwrith followed being a talmid of his) and it would do well to check him as well. Thus endeth my equivocation on my answer.