I experienced the same error:
This link talks about how to set up API key restrictions: https://cloud.google.com/docs/authentication/api-keys#adding_http_restrictions
In my case, the problem was that I was using this restriction:
HTTP referrers (web sites) Accept requests from these HTTP referrers (web sites) (Optional) Use *'s for wildcards. If you leave this blank, requests will be accepted from any referrer. Be sure to add referrers before using this key in production.
https://*.example.net/*
This means that URLs such as https://www.example.net or https://m.example.net or https://www.example.net/San-salvador/ would work. However, URLs such as https://example.net or https://example.net or https://example.net/San-salvador/ would not work. I simply needed to add a second referrer:
https://example.net/*
That fixed the problem for me.