Você deve adicionar sua própria variável de consulta personalizada primeiro:
function add_search_store_query_var($vars) {
$vars[] = 'search_store';
return $vars;
}
add_filter( 'query_vars', 'add_search_store_query_var');
E adicione a regra de reescrita:
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');
Você pode usar get_query_var('search_store'); para obter o termo de pesquisa.
Lembre-se de liberar as regras de reescrita antes de verificar - não funcionará sem regras de liberação. (Basta ir para permalink configurações e clique em salvar).
PS. Codificado diretamente aqui, então pode ser um pouco buggy.