There are some issues with WPML, it seems to work for some and fail for others. I will look into it as soon as I have the time for it, which won't be this week.
It's likely that the labels you find in WPML are actually the default values that are set in the wp-store-locator.php and not the ones that are loaded in the /frontend/class-frontend.php which are the ones used on the frontend.
I will try and fix it in the next release. One solution you could use, is to detect the used language ( I assume wpml sets a variable somewhere that allows you to check which language is current used, or get it from the url param? ) and then based on that set the $labels array content on line 224.
It's a bit of a hack solution. But until I figure out why it doesn't work with WPML, I think this is the only way to do it.