You ask:
My first question is where does the idea of wings come from: God obviously doesn't have wings, and humans either, why would divine beings have wings in terms of likeness to God?
Rambam explains that it is to necessitate a clear difference between Hashem and angels. We know that Hashem is incorporeal (refer to no. 3 of 13 Principles of Faith). However, in order to demonstrate that they are deemed a level below G-d they are described in a way that us as humans can more readily comprehend.
Rambam in Moreh Nevuchim Part I:49 states:
In order, therefore, to give to the mind of men the idea that the existence of angels is lower than the existence of God, certain forms of lower animals were introduced in the description of angels. It was thereby shown that the existence of God is more perfect than that of angels, as much as man is more perfect than the lower animals. Nevertheless, no organ of the brute creation was attributed to the angels except wings.
So why wings? Rambam continues:
Without wings the act of flying appears as impossible as that of walking without legs: for these two modes of motion can only be imagined in connection with these organs. The motion of flying has been chosen as a symbol to represent that angels possess life, because it is the most perfect and most sublime movement of the brute creation. Men consider this motion a perfection to such an extent that they themselves wish to be able to fly, in order to escape easily what is injurious, and to obtain quickly what is useful, though it be at a distance. For this reason, this motion has been attributed to the angels.
Rambam a bit later adds...
The motion of flying, frequently mentioned in the Bible, necessitates, according to our imagination, the existence of wings: wings are therefore given to the angels as symbols expressive of their existence, not of their true essence.
In a similar fashion, note the Abarbanel who says expressly:
שיוחס העופפות והכנפים למלאכים
That flying and wings are attributed to angels.
Like Rambam he explains that they are described with a limb that is similar to that of an animal so that it reduces their level compared to that of Hashem, in the same way that an animal is viewed as a lesser creation to that of a human.
As far as your third question:
why do angels need wings to fly around, either on earth or in the heavens
If we look at it in isolation i.e., not through the lens of the Rambam...
The Metzudas Dovid writes clearly:
יעופף. יעוף בשליחות המקום
He would fly - He would fly on the job/mission of Hashem
In other words, G-d created them with the means to carry out His tasks and did this through the means of flight. (Cross-reference Berachos 4b)
And possibly wings represent the most effective way to fly. Refer to the Radak there:
וכנפים הם סבת התנועה הממהרת מכל תנועות והוא העופפות
And wings - these are the reason for the swiftest movement from all movements and this is flight.
As far as your second question:
My second question is why wings are used to cover body parts and not garments or veil?
Firstly, just to ascertain why they needed to be covered. Rashi and the Metzudas Dovid explain that the face had to be covered so as not to look at the Shechinah, and the legs covered for modesty so that it will not show its whole body before their Creator. Additionally, the feet need to be covered so as not to act as a reminder of the Eigel HaZahav (the Golden Calf) as their feet resemble a calf's foot.
I can only suggest based on the Rambam, that angels are not described as wearing/owning any clothing (unless perhaps if they are in the form of a human), and as such it reverts to the one thing that us as humans can picture them with - their wings. Accordingly, these wings are the means through which they can "physically" cover themselves with.
