I have a WP Google Maps Connector addon available to Pro Pack users. The WP Google Maps plugin does have a store locator feature, and with the new Connector, you can choose to display your Connections Entries on the map.
Would you be interested in beta testing this Connector? The only reason it has not been released is that I need a few changes to the WP Google Maps plugin. I’ve requested them but have not heard anything back as of yet: