The error message "Failed to Geocode" appears when tool fails to fetch the coordinates of the provided address. There are a couple of things which can be the reason for this error message, first make sure "Street", "State", "City", and "Zipcode" are correctly provided for that address, if any of these are missing or wrong it will surely fail to fetch the coordinates due to validation. The second thing is we are using Google Geocoding service free API which has usage Limit per second as well as per day. The limit of the service is as follows.
WHAT TO DO IF I HAVE TOO MANY RECORDS?
If you have too many records to fetch, then there are two ways to do it,
1. Enable Billing for the API Key you're using for store locator. You will be charged $0.50 USD / 1000 additional requests, up to 100,000 daily.
2. Upload your records in chunks of 200 records each import file, but still per day limit will apply on it and you can't fetch more than 2500 records per day.