Application not found
This happened on my Nexus - you just have to reboot your device, and the Icon will show up.

Most likely Niantic changed the Launcher activity, so the short cut is no longer pointing to the correct activity, hence the error message.

Rebooting the device/restarting the launcher, and then re-adding the home screen shortcut will fix this.