Pretty Permalinks

You should add your own custom query variable first:

function add_search_store_query_var($vars) {
    $vars[] = 'search_store';
    return $vars;
}
add_filter( 'query_vars', 'add_search_store_query_var');

And then add rewrite rule:

function add_search_store_rewrite_rule() {
    add_rewrite_rule('stores/([^/]+)$', 'index.php?page_id=<YOUR SEARCH PAGE ID>&search_store=$matches[1]', 'top');
}
add_action('init', 'add_search_store_rewrite_rule');

You can then use get_query_var('search_store'); to get search term.

Just remember to flush rewrite rules, before you check it – it won’t work without flushing rules. (Just go to permalink settings and click save).

PS. Coded it directly in here, so it can be a little bit buggy.