Custom post type slug localization

First, you should have to register your custom post type with a generic, language-independent slug because the slug in register_post_type is not meant to be dynamic.

and then modify rewrite rule

try this snippet

function register_custom_post_type_services() {
    $labels = array(
        'name' => _x('Services', 'Post Type General Name', 'text_domain'),
        'singular_name' => _x('Service', 'Post Type Singular Name', 'text_domain'),
    );

    $args = array(
        'label' => __('Service', 'text_domain'),
        // ... other args
        'publicly_queryable' => true,
        'capability_type' => 'page',
        'show_in_rest' => true,
        'rewrite' => array('slug' => 'services-base'), // Generic slug
    );

    register_post_type('services', $args);
}
add_action('init', 'register_custom_post_type_services');

function custom_rewrite_rules_array($rules) {
    $newRules = array();
    $newRules['en/services/(.+)/?$'] = 'index.php?services=$matches[1]';
    $newRules['lt/paslaugos/(.+)/?$'] = 'index.php?services=$matches[1]';

    return $newRules + $rules;
}
add_filter('rewrite_rules_array', 'custom_rewrite_rules_array');

function custom_post_type_link($post_link, $id = 0, $leavename = false) {
    if (strpos('%services-base%', $post_link) === 'FALSE') {
        return $post_link;
    }
    $post = get_post($id);
    if (is_wp_error($post)) {
        return $post_link;
    }

    // Change 'services-base' based on language
    if (function_exists('pll_current_language')) {
        $language = pll_current_language();
        switch ($language) {
            case 'lt':
                $slug = 'lt/paslaugos';
                break;
            default:
                $slug = 'en/services';
                break;
        }
        return home_url($slug . "https://wordpress.stackexchange.com/" . $post->post_name);
    }

    return $post_link;
}
add_filter('post_type_link', 'custom_post_type_link', 1, 3);