We have a customer that I'm working with to rebuild their RDS farm from 2008R2 servers to 2016. Once I finished the initial deployment, I began testing the builds and realized pretty quickly that I couldn't open the start menu or use even use the search feature in the taskbar no matter what I tried.
I was using the same group policies that were currently applied on their existing farm thinking it should transition pretty smoothly, but that turned out not to be the case. I was eventually able to narrow it down to a single policy, but I also made the mistake of using Group Policy Management from their current 2008R2 management server, which I discovered later on complicated the troubleshooting since the setting causing the issue isn't visible from the 2008R2 console.
It ultimately turned out to be due to Applocker's Packaged App Rules. Since this had never been configured previously, there was no default rule to allow signed packaged apps that had been introduced in Server 2012 and later, and is what was ultimately breaking the Start button/Search feature.