Turning on autoflush on the handle worked for me (IIRC, this may require a use IO::File; on old Perls, before 5.14). Also please note the advice in Calling External Commands More Safely!

use warnings;
use strict;

open(my $Progress, '|-', qw/ zenity --title Explore --progress 
    --percentage 0 --text Test --auto-close --auto-kill /) or die $!;
$Progress->autoflush;
foreach my $Percent ( qw{10 20 30 40 50 60 70 80 90 100} ) {
    sleep 2;
    print "DBG> ", $Percent, "\n";
    print $Progress "$Percent\n";
    print $Progress "# Test $Percent\n";
}
close($Progress) or die $! ? $! : $?;
[download]

Update: And here's a version that handles the user clicking the "Cancel" button, which apparently causes a SIGHUP.

{
    my $run = 1;
    local $SIG{HUP} = sub { $run=0; };
    open(my $Progress, '|-', qw/ zenity --title Explore --progress 
        --percentage 0 --text Test --auto-close --auto-kill /)
            or die $!;
    $Progress->autoflush;
    print $Progress "# Test 0%\n";
    foreach my $Percent ( qw{10 20 30 40 50 60 70 80 90 100} ) {
        sleep 1 if $run;
        unless ($run) { print "Canceled\n"; last }
        print "DBG> ", $Percent, "\n";
        print $Progress "$Percent\n";
        print $Progress "# Test $Percent%\n";
    }
    close($Progress) or $run and die $! ? $! : $?;
    print "Done.\n";
}
[download]

Update 2: Minor edits to second example.