Yes, all mountains did have wings in the Krita Yuga. Hanumān, en route to Lanka over the seas in search of Sita, encounters the Maināka mountain in its human form standing on its own peak, and that is when Maināka introduces himself to Hanumān as the only mountain currently left with its wings still intact.
Vālmiki narrates the following in Sundara Kanda, Sarga 1:
O son! Earlier in the Krita yuga, mountains had wings. With speed equal to that of Garuda and Vayu, they went in all directions. [5-1-123]
After that when those mountains were thus flying freely, Devas and living creatures together with sages obtained fear in the doubt that those mountains might fall down. [5-1-124]
Then the angry Devendra who performed a hundred Asvamedha rituals, cut off the wings of thousands of mountains by his weapon vajra then and there. [5-1-125]
That Devendra angrily reached me with raised vajra. Then I was thrown away immediately by the great Vayu. [5-1-126]
O best among vanaras! With saved full wings, being thrown down into this salt ocean, I have been protected by your father. [5-1-127]
O chief among vanaras! Vayu is thus indeed respectable to me. For that reason I am respecting you. My this relationship with you has great virtues. [5-1-128]
As to your suggestion that the Lanka mentioned in the Vālmiki Rāmāyaṇa is same as the present day Sri Lanka, there's a question on that.