Is there any way for the Store Locator to also be able to search for business names within the system, or is it only address and city names that can be searched?
Yes, if you enable the Data Search option for the Menu item, you'll also be able to search by Name and/or Custom Field Data (depending on settings) on a string search basis.