There's no bug here, your state cache is fine (over 40k entries). It's just that a) AMDVLK doesn't have an own shader cache and b) the state cache is completely useless if the app compiles its D3D shaders on first use, which is basically what's happening here (same as Witcher 3, FFXV, and others).
You were right that's not a bug: I forgot that I created an empty amdPalSettings.cfg in etc folder which overwrites the config in my home folder. amdvlk actually has a disk shader cache, it just needs be turned on manually (just like pageflipping for vsync...):
https://github.com/GPUOpen-Drivers/AMDVLK/blob/master/README.md
Combination of driver cache and DXVK state cache makes situation somewhat acceptable for technical garbage like HotS. :)
Nothing extracted yet.
After each start of HotS, there is high CPU load and stutter due to the state cache apparently getting refreshed. However, the driver hasn't changed in between. Enabling amdvlk's disk shader cache doesn't improve the situation.
The game tends to compile lots of shaders only when they are used and thus always lead to stutter without driver shader cache, so turning off amdvlk's cache for testing purposes probably won't be helpful.
radv works correctly (state cache gets updated once and "sticks", stutter doesn't come back).
Latest HotS version
AMDVLK 2019.Q2.2
DXVK git 2245aada037c04ea52030b2288be6bff68c9a35a
RX 580
HeroesOfTheStorm_x64.dxvk-cache_1.zip
HeroesOfTheStorm_x64_d3d11.log
HeroesOfTheStorm_x64_dxgi.log