WordPress pagination not working with search page

by default, wordpress has it’s own main query in search page, in your case you didn’t changed the main query, and just create a custom query

paged is a reserved query variable which is used first by your main query, when your main query dosent have same results, you face a 404 error
you have 3 choices:

1. change paged variable

you can rename your page variable from paged to page or something else which is not used by wordpress by default

2. override 404 page

function override_404() 
{
    if ( is_search() && isset($_GET['s'])) {
        global $wp_query;
        $wp_query->is_404 = false;
    }
}
add_action('init', 'override_404');

3. override main query ( best )

function change_search_query() {
    if ( is_search() && isset($_GET['s'])) {
        $args = array();
        query_posts( $args );
    }
}
add_action('init', 'change_search_query');