Translating with WPML
WPML does not support string translations by default, first you will have to install the WPML string translations plugin.
1) Place the search shortcode somewhere visible on any page (or use the widget)
2) Open up that page, so the translations will get registered first
3) Open up the WPML -> String translation menu
4) Change the Select strings within domain option to "ajax-search-pro", so only strings from Ajax Search Pro are visible
5) That's it. Now the list will display all ajax search pro related translatable texts. All you need to do now is to translate them as you like :)
Please note that the number after each text in the Name column represents the search instance. This way different search instances with the same text can have different translations.