We are also running a 2019 RDS Farm and we have had this exact same issue with the Start Menu not working this week. Initially it was on one host, and now it is happening on two hosts! We ran the command on one host and it has fixed it. We have not ran it on the second host yet, as we had to stop it taking connections as it was causing so many issues for users.
Get-AppXPackage -AllUsers | Foreach {Add-AppxPackage -DisableDevelopmentMode -Register "$($_.InstallLocation)\AppXManifest.xml"}
Does MS know why this is happening? Has a Jan update caused this issue? It is very worrying since most of our staff are currently WFH and are relying on the RDS servers to be able to work effectively.
Many Thanks
Paul.