It looks like most new work permits were held by Ukrainians in 2016 (the last year I could find stats for). It's not easy to figure out any more detailed stats because Eurostat only gives a breakdown by country of origin for the total number of new permits (regardless of reason for the permit). But for Ukraine, it's somewhat easy because it leads on total number and on the ratio of work to other permits. More precisely, in 2016 there were 589K new permits to Ukrainians, and 82.7% were for work, so that gives about 487K new work permits issued to Ukrainians... but these were not all granted in 2016; the increase between 2015 and 2016 in the total number of new permits for Ukrainians was only 89K... yeah Eurostat data is really confusing on this. For re-issued permits... I don't know at all.
Actually, they do have breakdown (but only in a table, not in text):
That confirms my calculation for Ukraine. And we also find out that most of these Ukrainians (95% of them) went to work in Poland.
Also, second place for work permits went to India... wth 57K work permits, and the majority of these (53%) went to work in the UK... with rest much more thinly spread; Germany was the second destination for these Indians, but only took 8% of them.
Third place goes to the U.S. with nearly as many permits as for India, and a similar spread: 62% in the UK, followed by 10% who went to Germany.
4th place is for China, with 20K, but these had no clear concentration: 23% UK, 14.6% Germany etc.
5th place is Australia with 16K, who mostly (84%) went to the UK.
Very, very partial answer. I found stats for the origin of Blue Card holders for one year (2015). These are very probably not representative for other national-level schemes because they are seriously biased by Germany having issued most of these Blue Cards (for high-skilled workers), while in national-level schemes Poland and the UK both outweigh Germany; in 2015 there were 541,583 first-residence permits issued for work reasons in Poland vs 194,813 such permits in Germany, whereas for Blue Cards in the same year Poland issued 369 vs Germany's 14,620. Also the UK issued 633,017 such national-level permits in 2015, but doesn't even take part in the Blue Card scheme. With that big disclaimer, here is breakdown:
So most (40%) were granted to applicants from Asia (excluding the middle East), then come non-EU European countries from the South-East (25%), followed by the Middle-East (incl. Turkey and North-Africa) with 18% and then the Americas (14%): 8% South, 6% North. Tailing were Sub-saharan africa with 2% and Oceania with 1%.