First, make sure you have you read and followed the instructions for WPML integration found at https://community.algolia.com/wordpress/wpml.html
Following those instructions will ensure that the content itself has a wpml.locale attribute in the index for faceting, and will expose a window.current_locale
JS variable in the page, which you can use for further customization.
From there you should be able to customize the Algolia JS widgets in the autocomplete.php and instantsearch.php templates for your use case.
There is additional documentation about customizing those templates here https://community.algolia.com/wordpress/customize-autocomplete.html and here https://community.algolia.com/wordpress/customize-search-page.html.
The following example(s) extend what is described in the references above, to provide translations for the labels in the autocomplete drop down.