Your original code...

use strict;
use Win32::OLE;
use Win32::OLE qw(in with);
use Win32::OLE::Const 'Microsoft Word';
use Constant 'True' => 1;
use Constant 'False' => 0;
$Win32::OLE::Warn = 2; # Throw Errors, I'll catch them

my $word = Win32::OLE->GetActiveObject('Word.Application') || 
        Win32::OLE->new('Word.Application', 'Quit');

my $mydoc = $word->activedocument; 
my $rng = $mydoc->{range};

$rng->find->clearformatting;
$rng->find->font->{'Bold'}= "True";
$rng->find->replacement->clearformatting;
$rng->find->execute({findtext=>"[0-9]{1,}",  wrap=>wdFindContinue,
             replacewith=>"<bold>^&</bold>", matchwildcards=>'True', 
            replace=>wdReplaceAll});
[download]

I've tried your code in Word (as a user) and it works. For anyone reading this, ^& is whatever Find just found/matched against.

Recording a macro suggests the code:

use strict;
use Win32::OLE;
use Win32::OLE qw(in with);
use Win32::OLE::Const 'Microsoft Word';
use Constant 'True' => 1;
use Constant 'False' => 0;
$Win32::OLE::Warn = 2; # Throw Errors, I'll catch them

my $word = Win32::OLE->GetActiveObject('Word.Application') || 
        Win32::OLE->new('Word.Application', 'Quit');

my $mydoc = $word->activedocument; 
my $Selection = $word->{Selection};

$Selection->Find->ClearFormatting();
$Selection->Find->Font->{Bold} = True;
$Selection->Find->Replacement->ClearFormatting();
with ($Selection->Find->Replacement->Font,
    Bold => True,
    Italic => False );

$Selection->Find->{Text} = "[0-9]{1,}";
$Selection->Find->Replacement->{Text} = "<bold>^&</bold>";
$Selection->Find->{Forward} = True;
$Selection->Find->{Wrap} = wdFindContinue;
$Selection->Find->{Format} = True;
$Selection->Find->{MatchCase} = False;
$Selection->Find->{MatchWholeWord} = False;
$Selection->Find->{MatchWildcards} = True;
$Selection->Find->{MatchSoundsLike} = False;
$Selection->Find->{MatchAllWordForms} = False;

$Selection->Find->Execute( {Replace=>wdReplaceAll} );
[download]