I wouldn't try to localize your slugs.  Instead, why not give your users the option to change them by adding another field to the permalink settings page?

Hook into `load-options-permalink.php` and set up some things to catch the `$_POST` data to save your slug.  Also add a settings field to the page.

    <?php
    add_action( 'load-options-permalink.php', 'wpse30021_load_permalinks' );
    function wpse30021_load_permalinks()
    {
    	if( isset( $_POST['wpse30021_cpt_base'] ) )
    	{
    		update_option( 'wpse30021_cpt_base', sanitize_title_with_dashes( $_POST['wpse30021_cpt_base'] ) );
    	}
    	
    	// Add a settings field to the permalink page
    	add_settings_field( 'wpse30021_cpt_base', __( 'CPT Base' ), 'wpse30021_field_callback', 'permalink', 'optional' );
    }

Then the call back function for the settings field:

    <?php
    function wpse30021_field_callback()
    {
    	$value = get_option( 'wpse30021_cpt_base' );	
    	echo '<input type="text" value="' . esc_attr( $value ) . '" name="wpse30021_cpt_base" id="wpse30021_cpt_base" class="regular-text" />';
    }


Then when you register your post type, grab the slug with `get_option`.  If it's not there, use your default.

    <?php
    add_action( 'init', 'wpse30021_register_post_type' );
    function wpse30021_register_post_type()
    {
    	$slug = get_option( 'wpse30021_cpt_base' );
    	if( ! $slug ) $slug = 'your-default-slug';
    	
    	// register your post type, reference $slug for the rewrite
    	$args['rewrite'] = array( 'slug' => $slug );
    	
    	// Obviously you probably need more $args than one....
    	register_post_type( 'wpse30021_pt', $args );
    }

Here's the settings field portion as a plugin https://gist.github.com/1275867

**EDIT: Another Option**

You could also change the slug based on what's defined in the `WPLANG` constant.

Just write a quick function that holds data...

    <?php
    function wpse30021_get_slug()
    {
    	// return a default slug
    	if( ! defined( 'WPLANG' ) || ! WPLANG || 'en_US' == WPLANG ) return 'press';
    	
    	// array of slug data
    	$slugs = array( 
    		'fr_FR'	=> 'presse',
    		'es_ES' => 'prensa'
    		// etc.
    	);
    	
    	return $slugs[WPLANG];
    }

Then get the slug where you register your custom post type.

    <?php
    add_action( 'init', 'wpse30021_register_post_type' );
    function wpse30021_register_post_type()
    {
    	$slug = wpse30021_get_slug();
    
    	// register your post type, reference $slug for the rewrite
    	$args['rewrite'] = array( 'slug' => $slug );
    
    	// Obviously you probably need more $args than one....
    	register_post_type( 'wpse30021_pt', $args );
    }

The best option, IMO, would be to both give the user an option and provide solid defaults:

    <?php
    add_action( 'init', 'wpse30021_register_post_type' );
    function wpse30021_register_post_type()
    {
    	$slug = get_option( 'wpse30021_cpt_base' );
    	// They didn't set up an option, get the default
    	if( ! $slug ) $slug = wpse30021_get_slug();
    
    	// register your post type, reference $slug for the rewrite
    	$args['rewrite'] = array( 'slug' => $slug );
    
    	// Obviously you probably need more $args than one....
    	register_post_type( 'wpse30021_pt', $args );
    }