I managed to solve this issue by following the solution found here: https://community.spiceworks.com/topic/2213938-windows-10-start-menu-process-freezing-after-1903-upgrade
We had this group policy set to "disabled" : "Computer Config \ Policies \ Admin Templates \ System \ Group Policy \ 'Continue experiences on this device'" Setting it to "Not Configured" solved the issue with the start menu for us.