My experience on both my macs is similar. My two Windows 10 parallels VMs (in place upgrades from Win 7) are plagued with the start menu issue, but my two standalone fresh install Windows 10 Bootcamp partitions (not linked to Parallels) have never had it.
BUT Windows forums are full of the same problem so it is not simply a Parallels problem.
I suspect there are multiple causes and some of those may be associated with Parallels. A combination of reverting to snapshots, repeating updates, and the reported fixes have always worked so far, but unfortunately, once solved the problem is highly likely to recur at some point.
Last edited: Mar 25, 2016