Dude, i had the same problem.
The first time, i uninstalled this apps directly from Start Menu by right click-> uninstall. But whenever i restarted my pc, the apps icons still in Start Menu.
I had to click on to the apps in the Start Menu, automatically Windows Store re-downloaded and re-installed apps.
So then:
- Open Settings.
- Click Apps.
- Click Apps & features.
- Locate the applications you are trying to uninstall.
- Click Uninstall.
Thats it!
Sorry about the english
Saludos desde Chile