Are you connecting via wifi or mobile data? If it happens on both then I'd say it has something to do with your Google account, if you get that error on one but not the other then it's network specific and has nothing to do with your phone. It could be that another device on that subnet does indeed have a malware intrusion that is causing what Google perceives to be a DOS attack and has blacklisted it from their servers.
You could also try to install
Bing search to see if the block is at Google or through your carrier/isp.