Unlike WPML, Polylang supports string translations natively.
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 Settings -> Languages menu
4) Navigate to the String Translations panel, and change the View all groups 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.