I was getting the 'Critical Error: Start menu & Cortana...' error about every third time I restarted my computer. Now I think I have found a solution (at least one that worked for me).
By chance, are you using a PIN or your face to log in to the system? Try changing the method to your actual password. I did it just by idle curiosity about two weeks ago and realized I haven't gotten the error since. I didn't even have to uninstall my antivirus (which is AVAST, by the way) or install any other program. Of course, YMMV.
Hope that helps.