Search – Ajax – Alter Query Parameters with Pagination

I think this is what you want. base is set via home_url(), format is page/%#%/, search query arg is added via add_args if it exists:

$args = array(
    'base' => home_url( '/%_%' ),
    'format' => 'page/%#%/',
    'current' => max( 1, get_query_var('paged') ),
    'total' => $temp->max_num_pages,
);

if( isset($_GET['s']) ){
    $args['add_args'] = array(
        's' => $_GET['s'] // your search query passed via your ajax function
    );
}

echo paginate_links( $args );