Classic Shell caches the menu icons inside the DataCache.db and some information related to frequent programs. Every time the menu is closed it saves the entire cache file. Datacache.db is usually always stored locally at %localappdata%\ClassicShell\ directory. In your case you are using XenDesktop and your user profile and thus the AppData folder is redirected so you are experiencing Start Menu slowdowns since your network speed may be slow (not as fast as a local directory anyway).
You could try using a solution like
Citrix Profile Management to allow certain folders to be copied to the local system. Or not redirect the appdata folder at all. Also see this article:
Citrix Profile Management and VDI – Doing it Right! Appdata redirection is a debatable topic. You can decide after reading the pros and cons:
Should AppData be Redirected or Left in the User Profile?Please report back if you did any changes and if that helped.