Have you tried taking Moose and namespace::autoclean out of the picture?

Once I remove them and fix the remaining code, it works:

#!/usr/bin/perl 
use 5.012003;   # Perl version requirement
#===========================================================
# Percentage CLASS (script below)
#===========================================================
package Percentage;
#use Any::Moose; 
#use namespace::autoclean; 

sub new {
    my $class = shift;
    bless { int => @_ } => $class;
};

use overload 
    q{""} => \&to_string,
    '0+'  => \&to_num,
    '+'   => \&add;

sub to_string {
    my $self = shift;
    print "to_string()\n";
    return $self->int();
}

sub to_num {
    my $self = shift;
    print "to_num()\n";
    return $self->int();
}

sub add {
    my ($left, $right) = @_;
    print "add()\n";
    my $result = new Percentage( $left->int() + $right->int() );
    return $result;
}

sub int { $_[0]->{int} }

1;

#===========================================================
# SCRIPT
#===========================================================
package Example::Script;
use 5.012003;   # Perl version requirement
use strict;
use warnings;
                           # printed in output :
my $a = new Percentage(2); # build
my $a_num = $a->int();     #
print "$a\n";              # Percentage=Hash(0x11cfe8c)
print "$a, $a_num\n";  # Percentage=Hash(0x11cfe8c), 2

my $b = new Percentage(3); # build
my $c = $b + $a;           #
print "$b, $c\n";          # Percentage=Hash(0x116912c), 3693356
__END__
to_string()
2
to_string()
2, 2
add()
to_string()
to_string()
3, 5
[download]

I assume that something somewhere within Moose(::Any) or namespace::autoclean messes up the overloading. Maybe the bug reports or feature limitations tell a clearer story.

Update: Searching Moose for overload points me to Class::MOP::Class, which has an API to introspect overloading. Maybe consult that to find out whether your class actually has overloading, or maybe Moose / MOP want you to set up all your overloading through this mechanism instead of overload directly.