You might want to restructure your code such that the menu() function only returns the selection instead of immediately executing it.

Then, you would have a main loop that repeatedly invokes menu() and then executes the choice:

sub menu {
    return int(rand(4)+1);
}

our $main_menu = [
         [ "Second Menu", sub{ $current_menu = $menu2 } ],
];

our $menu2 = [
         [ "Return", sub{ $current_menu = $main_menu } ],
];


sub mainloop {
    do {
        my $choice = menu();
        $m->[$choice]->[1]->();
    } while( $choice != 4 );
}
[download]

To incorporate the second menu, you could either have a reference to the "current menu", or a second "main"loop:

our $current_menu;

sub menu {
    for my $entry (@$current_menu) {
        say $entry->[0];
    };
    return int(rand(@$current_menu)+1);
}

sub mainloop {
    do {
        my $choice = menu();
        $current_menu->[$choice]->[1]->();
    } while( $choice != 4 );
}
[download]