Google announced some changes to the Google Maps APIs authentication and usage limits.
Usage of the Google Maps APIs now requires a key. If you are using the Google Maps API on localhost or your domain was not active prior to June 22nd, 2016, it will require a key going forward. This is why such error occurs.
In order to deal with the error, please, complete the following:
Log into your Magento Admin and navigate to System -> Configuration -> TemplateMonster -> Google Map.
You will see the Embed Google Map settings section which stands for the display of the map in the footer of all pages except for the contact page and Contacts Map Settings section which is for the Contact Us page Map.
The second field is called API key, where you should enter a Google API Key which is necessary for the correct work of the map.
You can get your personal Google API key at this page.
Press Get a key > Select or Create Project > Enable API button, copy your key to use in Magento and click on Finish.
Note: API key should be entered to both Embed Google Map and Contacts Map Settings separately.
Press the Save Config button and reload the page.
Feel free to check the detailed video tutorial below: