I would probably go the route of manipulating the -choices array.

#!/usr/bin/perl -w
use strict;
use Tk;
use Tk::BrowseEntry;

my $mw = MainWindow->new();

my $sel = '';
my @choices = qw(1 2 3 4 5 6 7);

my $mb;  #declare it first so can call it in callback
$mb = $mw->BrowseEntry(
 -label    => 'List One',
 -choices  => \@choices,
 -variable => \$sel,
 -browsecmd=>sub{
      #print "@_\n";
      my $selected = $_[1];
      #print "$selected\n";
      @choices = grep { $_ ne $selected } @choices; 
      $mb->configure(-choices => \@choices);
#      print "@choices\n"; 
                 }
)->pack();

MainLoop;
[download]