You're pretty close. Try it with this minor change:

my $line='*Mary* had a little lamb';

my $bagofwords='had|a|Sam|Tom';

while ($line=~s/\*([^\*]+)\*\s($bagofwords)\s+/*$1_$2* /) {
    print "$line\n"; # debug
}
__END__
*Mary_had* a little lamb
*Mary_had_a* little lamb
[download]