To summarize the problem:
* SK appears to be using Amazon Cloud services to host its servers.
* A significant part of Amazon IPv4 range is blocked in my country.
* Running a full VPN solution means running Steam through it, which is explicitly forbidden in Steam ToS.
I was unable to make SK use proxy.