We had a deep look into WPML, but unfortuantely it is not possible to use WPML with custom Database Queries (needed to lat / lng <-> distance).
It is possible to translate everything with WPML except the stores data (like name, description).
You can read more about this here: https://wpml.org/forums/topic/display-custom-types-based-on-language-in-a-custom-plugin/