I've made a few changes to your setup, and I will explain why.
1. You had Caching (Caching options) and Custom ajax handler activated (Compatibility options). The problem with these is that caching is not yet WPML ready, and the custom ajax handler only loads the most neccessary plugin events – and WPML loading is not registered as one. This resulted in passing the wrong language code to the search, so I had to turn these options off.
2. The Advanced Ajax Page loader options were enabled. I've turned them off, now it should work as expected.
3. and 4. You have to exclude the categories on the Advanced Options panel. (you will see if you scroll down). The Frontend search options are only for appearance. I see you excluded a few categories on the General Options -> Sources panel, but that options is related to something else (when categories are results).Best,
If you like my products, don't forget to rate them on codecanyon :)