The search icon isn’t a part of the actual menu, at least it isn’t generated by the WordPress menu function. To get the selector exactly where you want might require using a function in the PHP where it’s wanted.
Do you now if WPML includes a function that can be inserted in the code to add the language selector? We may need access to that. If it exists I can give you instructions on where in the theme to add this function.
I have sent an email to find out more about any possible conflict with UberMenu Lite and well see if that could be effecting this in any way.