I was able to resolve this problem with Shopify’s support. The short answer is: try using a different browser.
While chatting with the agent, I found out that if I try to edit the shipping zone from Mozilla Firefox I do not see the five individual countries in UK, only one entry “United Kingdom”. But when I switched to Google Chrome, I discovered that now United Kingdom has five provinces: British Forces, England, Northern Ireland, Scotland, and Wales. I could select all of them and this fixed the problem.
Hope this helps!