Hello,
If you are using UPD(user profile disk), you can try modifying the registry to solve this issue as suggested in Start button and Search functionality stopped working in RDS server - Microsoft Q&A and Windows 2019 RDS Servers Start Menu Stopped Working - Microsoft Q&A
Run below commands:
reg delete HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\FirewallRules /va /f
reg delete HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\RestrictedServices\Configurable\System /va /f
reg delete HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\SharedAccess\Parameters\FirewallPolicy\RestrictedServices\AppIso\FirewallRules /va /f
Please note, for added protection, back up the registry before you modify it. Then, you can restore the registry if a problem occurs.
Regards,
Karlie