So the first problem is that by default no data is returned saying which category a location is assigned to. You can fix this by adding code like this to the functions.php in your theme folder. It uses the wpsl_store_meta filter, which allows you to include custom data for each location.
This code will only include the first term name, if you want to know all the term names you will have to loop over the $terms and grab all the term names.
Once all the location is collected, you can modify it with the wpsl_store_data filter ( no documentation yet ). What you can do is go through the collected data and use array_multisort to sort the results alphabetically by category name.
This doesn’t work perfect in this case, because when it does the sorting it will place locations with empty terms above locations that do have terms set.
I think there are two ways to fix this issue. One of them is to set the default $store_meta[‘terms’] = ”; always to ‘x’, so when the alphabetical sorting is done they will always end up at the bottom. But this will mess with the distance ordering.
Another fix would be to loop over the results again, create two arrays with one holding the locations with the categories set, and the other one with the empty categories. Then merge them together, but make sure the one that does have the categories set is placed before the array holding the locations with no categories.