For some sites in German I use the following plugin to translate page to seite (the German word for page):

<?php # -*- coding: utf-8 -*-
/**
 * Plugin Name: T5 Page to Seite
 * Description: Ersetzt <code>/page/</code> durch <code>/seite/</code>.
 * Author:      Thomas Scholz <[email protected]>
 * Author URI:  http://toscho.de
 * License:     MIT
 * License URI: http://www.opensource.org/licenses/mit-license.php
 */

if ( ! function_exists( 't5_page_to_seite' ) )
{
    register_activation_hook(   __FILE__ , 't5_flush_rewrite_on_init' );
    register_deactivation_hook( __FILE__ , 't5_flush_rewrite_on_init' );
    add_action( 'init', 't5_page_to_seite' );

    function t5_page_to_seite()
    {
        $GLOBALS['wp_rewrite']->pagination_base = 'seite';
    }

    function t5_flush_rewrite_on_init()
    {
        add_action( 'init', 'flush_rewrite_rules', 11 );
    }
}

Note that you flush the rewrite rules on de/activation only. You will need a separate rewrite rule in your .htaccess to redirect old URLs to the new ones:

RedirectMatch Permanent ^/(.*)/page/(.*) /$1/seite/$2

For some sites in German I use the following plugin to translate page to seite (the German word for page):

<?php # -*- coding: utf-8 -*-
/**
 * Plugin Name: T5 Page to Seite
 * Description: Ersetzt <code>/page/</code> durch <code>/seite/</code>.
 * Author:      Fuxia Scholz
 * License:     MIT
 * License URI: http://www.opensource.org/licenses/mit-license.php
 */

if ( ! function_exists( 't5_page_to_seite' ) )
{
    register_activation_hook(   __FILE__ , 't5_flush_rewrite_on_init' );
    register_deactivation_hook( __FILE__ , 't5_flush_rewrite_on_init' );
    add_action( 'init', 't5_page_to_seite' );

    function t5_page_to_seite()
    {
        $GLOBALS['wp_rewrite']->pagination_base = 'seite';
    }

    function t5_flush_rewrite_on_init()
    {
        add_action( 'init', 'flush_rewrite_rules', 11 );
    }
}

Note that you flush the rewrite rules on de/activation only. You will need a separate rewrite rule in your .htaccess to redirect old URLs to the new ones:

RedirectMatch Permanent ^/(.*)/page/(.*) /$1/seite/$2