Hello,
This message is super misleading, and I wish Microsoft would have changed its messaging here. It doesn't mean the app is not Microsoft verified, it is more about the app is not downloaded through the Store App.
Go to Settings > Apps > Advanced App Settings. Do you see "Choose where to get apps"? If you do, choose "Anywhere" here.
If you cannot find that option, it can mean that your Windows is in S mode. Type winver in the search on the taskbar and hit enter, a pop up window will provide you with some information about whether it is S mode. If it is, please use this instruction to switch out of S mode first.