Google App "search pending" notification stuck on Marshmallow
When you try to uninstall the Google app, it would ask you if you want to replace the app with the factory version. Select yes. That should do it, worked for me. :)