Solution
KernelShark needs several UI libraries to run in UI mode. You need to run these commands after step 4 (installing KernelShark through apt):
sudo apt install desktop-file-utils
sudo apt install libqt5gui5 libqt5widgets5 libqt5network5 libgles2-mesa-dev
After that KernelShark should be available in the Windows Start-menu.