Frontend

Any user with the appropriate roles/capabilities can add and edit stores. You can use a user role plugin to assign the appropriate capabilities. You can also limit their ability to edit/delete each others stores.

The roles are pretty well self explanatory.

Worth mentioning this isn’t exactly “frontend”. They would use the dashboard

There’s no build in tool / add-on available at the moment that makes this possible, but if your comfortable with code you can use a contact form ( any will work as long as they have filters to allow you to do something with the submitted data ) with custom fields that on submit saves the data in the corresponding meta fields from the store locator plugin.

This solution does require you to be comfortable with code.