Thanks for the update and details.
1.Kindly confirm what update or other changes you 've made before the issue occurrence.
2.From the error message, it indicated the problem was related to certificate used in remote connection.
Is there any icon you could click to view the certificate when the error message prompted?
3.Is it possible to check if any settings have been changed on the target computer or server?
4.Instead of remoting from windows store app but type in mstsc by right clicking run button from start menu.
After then configure the user account, remote computer or Gateway if any and verify if the remote connection would work.
If not working, click save as to get a .rdp file and navigate to authentication level:i:value with notepad and change it to 0:
If the Answer is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.