Best and easiest way to rewrite the search and paginatin base?

Hey guys,

All I have in my functions.php right now is this pagination function:

/**
 * Pagination links for search and archives
 */

function get_pagination_links( $type = 'plain', $endsize = 1, $midsize = 1 ) {
    global $wp_query, $wp_rewrite;
    $wp_query->query_vars['paged'] > 1 ? $current = $wp_query->query_vars['paged'] : $current = 1;

    // Sanitize input argument values
    if ( ! in_array( $type, array( 'plain', 'list', 'array' ) ) ) $type = 'plain';
    $endsize = (int) $endsize;
    $midsize = (int) $midsize;

    // Setup argument array for paginate_links()
    $pagination = array(
		'base'			=> @add_query_arg('paged','%#%'),
		'total'			=> $wp_query->max_num_pages,
		'current'		=> $current,
		'show_all'		=> false,
		'end_size'		=> $endsize,
		'mid_size'		=> $midsize,
		'type'			=> $type,
		'prev_next'		=> false,
		'paged'			=> get_query_var( 'paged' )
    );

	return paginate_links( $pagination );
}

My search-form looks like this:

<form class="search-form" action="<?php echo home_url( '/' ); ?>" method="get">
    <fieldset>
		<div class="input-inside-label">
			<label for="s">Suchen …</label>
			<input type="text" name="s" class="s" value="<?php the_search_query(); ?>" />
		</div>
		<button type="submit" class="search-button">Suchen</button>
    </fieldset>
</form>

What I wanna do:
I’d like to rewrite the standard /?s= to the german word /suche

So when searching for “test” I want my URL to look like this:
www.mydomain.com/suche/test

Moreover I’d like to rewrite the pagination as well …
So when searching for test and clicking on page 2 I’d like the address to look like this …

www.mydomain.com/suche/test/seite/2

So in essence I’d like to rewrite /?s= to the german word suche (for search)
And rewrite &paged=2 to the german word seite (for page)

As you can see all I have in my code right now is the sample above because I removed all other trials – I couldn’t seem to make it work.

Any clever ideas on that? I’m using the latest wordpress version and would love to find a filter-based solution. I don’t want any JS to interact with the search-form.

Thank you in advance