The map shows the icon of the Default category, generally, and that setting is only available if the CPT field for Category is set to use “Ajax Chained” instead of select or other options.
In addition, when a listing is added to more than one category, Google Maps script will use the icon of the category with lower ID. Unfortunately we have no control over that, as it is a method of the GMaps API. In many cases this means that a parent category, created first, logically, often has a lower ID.
It is not sufficient to delete and then re-add categories to change their ID. Instead, listings must be exported and then deleted from the site, categories recreated, and then listings imported again to set the ‘new’ categories.
Test for yourself by setting a listing with a Default category with a high cat id and then a second category with a low cat id.
Category IDs can be seen on the category settings page at:
Places (CPT) – Categories