While I've finally fixed this issue I'm not sure which of the steps I did had the right impact. Therefore… worst case scenario … do it all.
This actually unregisters PowerShellGallery and registers it back. This should work when the bug in PowerShellGet will be fixed.
This actually unregisters PowerShellGallery and registers it back but as an alternative source. It adds missing slash so make sure you add it with https://www.powershellgallery.com/api/v2/, not https://www.powershellgallery.com/api/v2
This issue can be visible on the screen below. First, we have a working PowerShell Repository, then it's unregistered and when you register it back it's missing slash.
This is my top choice to fix this. I actually did this couple of times with closing PowerShell window and without getting always same message. Finally I went for reboot. Which makes sense because the very package responsible for updating was busy updating.
As with any critical system problems a reboot is good way to have a clean start. Some settings can't update while system is running.