Custom permalink for search and pagination

I believe the primary reason that the GET parameter format is still used for searches is that search forms are regular GET forms that when submitted form URLs with the GET parameters appended.

But a further problem with using custom URLs to capture searches is that search terms can be arbitrary text, including slashes, etc, which can look ugly when baked into a URL.

Suppose we used your desired search URL format:

mysite.com/suche/term

And I searched for the term "belegte brot", with the quotes. We end up with the URL:

mysite.com/suche/%22belegte+brot%22

Which isn’t terribly pretty, and similar escaping needs to be done for any other special characters.

Nevertheless, it’s still possible to achieve the permalink structure you are looking for.

Step 1: Register permalink structure

Hook on generate_rewrite_rules action, to add new patterns:

function my_generate_rewrite_rules( $rewrite ) {
    $rewrite->rules = array_merge( array(
        'suche/([^/]+)(?:/seite/(\d+))?/?' => 'index.php?s=".$rewrite->preg_index(1)."&paged='.$rewrite->preg_index(2)
    ), $rewrite->rules );
}
add_action( 'generate_rewrite_rules', 'my_generate_rewrite_rules' );

This registers a rule at the very top of the rewrite rule stack, which will capture URLs of the forms suche/<term>, suche/<term>/, seite/<term>/seite/<page> and seite/<term>/seite/<page>/ and transform them into the query variables s=<term> and paged=<page>

Step 1a: Regenerate permalinks by visiting the Settings > Permalinks page in the WP admin area.

Step 2: Insert JavaScript in your search form that will, instead of submitting a form using GET parameters, will instead redirect to a URL of the form above:

<form id="search" action="<?php echo home_url( '/suche/' ); ?>">
    <input name="s" />
</form>
<script>
    jQuery('#search').submit(function(ev) {
        ev.preventDefault();
        location.href = jQuery(this).attr('action') + escape( jQuery('#search').find('[name="s"]').val() );
    });
</script>

This example shows a form whose submit event is captured and cancelled, instead updating the URL. NB: This is untested.

Step 3: Add a hook on the get_pagenum_link filter to form the expected URLs:

function my_search_pagenum_link( $link ) { 
    if( !is_search() )
        return $link;    // Do nothing unless on a search

    // Attempt to parse the page number from the provided URL
    if( !preg_match( '#/page/(\d+)#', $link, $matches ) )
        return $link;

    // Return a re-formed URL
    return home_url( '/suche/' . urlencode( get_query_var( 's' ) ) . '/seite/' . $matches[0] );
}
add_filter( 'get_pagenum_link', 'my_search_pagenum_link' );

This should be sufficient to achieve your desired behavior.