Symptoms

No network access from the WSL to the Internet. Both domain and IP based ping commands failed. Other advices from the Internet does not help. Newly installed distro from the Store has same problems as well.

Cure (in my case at least)

1. Backup distros you need (See Backup section)
2. Uninstall an each installed distro
3. Go to Apps -> Programs and Features -> Turn Windows features on or off, make a screenshots of the current state and ensure next features unchecked:
   
   1. Virtual Machine Platform (Since it was on my Windows Home)
   2. Windows Hypervisor Platform (might be required if was in use)
   3. All Hyper-V related features maybe (in order of Windows Pro)
   4. Windows Projected File System
   5. Windows Subsystem for Linux
4. Turn off your PC and then turn in on. Preffered than Reset in order to trully reset thirdparty hardware like network controllers (Wi-Fi/Ethernet)
5. Reset your network settings:
   
   1. Run CMD as an Admin and execute commands from the "Network Reset Commands" section bellow
   2. Hit "Windows" key, type "Network reset" and hit "Enter". Click "Reset now" button.
6. Turn off your PC and then turn in on
7. Go to Store and install not required distro (Debian in my case since I'm using a Ubuntu)
   
   1. Start distro from the Store by clicking an appropriate button
   2. Ensure that ping is working properly
8. Restore previously backupped distros (See Restore section)

Network Reset Commands

ipconfig /flushdns (Clear the dns cache)  
nbtstat -RR (release and refresh NetBIOS names)  
netsh int ip reset (reset ip settings)  
netsh winsock reset (Reset Winsock Catalog)  
netsh interface ip delete arpcache (reset Address Resolution Protocol cache)  

Sources

1, 2