Unfortunately (at least free version) the plugin is quite dumb in this matter.
You need to manually edit following file:
/www/wp-content/plugins/ap-google-maps/js/arrow-google-maps.js
and replace all instances of original key with yours:
https://maps.googleapis.com/maps/api/js?v=3&key=YOUR_KEY_HERE&...
where “YOUR_KEY_HERE” is your Google Maps API key.