add_rewrite_rule not working for language specific characters

This is happening due to encoding. I assume you have a function in your search page, which you get and use search_text inside that template. You should decode the URL before doing so.

The urldecode() function would be what you are looking for. Your string is also UTF-8 encoded, so this is what you are going to need:

$string = utf8_decode( urldecode( $_GET['search_text'] ) );

Now you can use the decoded string in your search.