s///ge works for me

use warnings;
use strict;
use Term::ANSIColor;

my $word = 'bob';
my $sentence = 'bob said hi to bob';
print "$sentence\n";

$sentence =~ s/($word)/colored($1, 'bold')/ge;
print "$sentence\n";

print color('reset');
print "done\n";
[download]