"... is there a way to modify the Label of the pop-up buttons by clicking on my button "Change popup" without having to recreate my popup?"

Yes. You can add a '-postcommand' callback which uses the 'entryconfigure()' method to modify '-label'. All described in the Tk::Menu documentation.

In the example script below, you'll start with labels "A" and "B". These persist until the "Change me" button is used: the labels then change to "C" and "D". Using the "Change me" button again toggles these back to "A" and "B", and so on. If you don't want this toggling effect, disable the "Change me" button after the first use.

Some additional notes:

• I've used an anonymous block to limit the scope of the lexical variables '@labels' and '$label_group'. Now, only '&change_label_group' can change their values; and '&add_edit_popup' can read their values. They are invisible to the rest of the code and can't be inadvertently accessed.
• I've used an 'INIT' block to initialise the values for '@labels' and '$label_group'. Without this (or some equivalent such as a 'BEGIN' block) they are declared but undefined. See "perlmod: BEGIN, UNITCHECK, CHECK, INIT and END" if you're unfamiliar with this.
• I've changed the menu commands to something that works for testing. This is not part of the code to modify the labels. Your original code is still there but commented out.
• The '-postcommand' callback calls 'entryconfigure()' every time the menu is posted. You might want to add a flag to only do this if the "Change me" button is used.
• Other than code additions, two lines commented out, and the shebang line for my use, I've left your posted code intact.

Here's the working, example script:

#!/usr/bin/env perl

use warnings;
use strict;
use Tk;

my $mw = MainWindow->new;
my $text = $mw->Text()->pack;

add_edit_popup($mw, $text);

my $but = $mw->Button(
    -text => "Change me", 
    -command => \&push_button,
);

$but->pack();

MainLoop;

{
    my (@labels, $label_group);
    INIT {
        @labels = ([qw{A B}], [qw{C D}]);
        $label_group = 0;
    }

    sub change_label_group {
        $label_group = $label_group ? 0 : 1;
        return;
    }

    sub add_edit_popup
    {
      my ($mw, $obj) = @_;
      my $menu = $mw->Menu(-tearoff=>0, -menuitems=>[
            #[command=>"Move col to the right", -command=>[sub {MoveCo
+lumn('right')}, $obj,]],
            #[command=>"Move col to the left", -command=>[sub {MoveCol
+umn('left')}, $obj,]],
            [command=>$labels[$label_group][0], -command => sub { prin
+t "right\n" }],
            [command=>$labels[$label_group][1], -command => sub { prin
+t "left\n" }],
            ]); 
      $menu->configure(-postcommand => sub {
            for my $i (0 .. $menu->index('last')) {
                $menu->entryconfigure($i, -label => $labels[$label_gro
+up][$i]);
            }
        },
      );
      $obj->menu($menu);  
      $obj->bind('<3>', ['PostPopupMenu', Ev('X'), Ev('Y'), ]);
      return $obj;
    }
}

sub push_button{
#change/configure
#command=>"Move selected column to the right"
#command=>"Move selected column to the left",
    change_label_group();
}
[download]

Finally, a couple of recommendations. Consider using more meaningful names (e.g. 'push_button' is a poor choice). Avoid global (file-scoped) lexical variables (e.g. '$text'); instead, use the smallest, lexical scope possible.