I'm guessing it's to do with the fact that 'lama' has two a's? Is it possible to easily amend this code to handle this case?

Yes, and it's a trivial amendment. Just deploy the /g modifier:

#!/usr/bin/perl

use strict;
use warnings;

my @words = <DATA>;
chomp @words;

while ( @words >= 2 ) {
    my $model = my $regex = shift @words;
    if ( $regex =~ s/(.*?)[ab](.*?)/$1\[ab\]$2/g ) {
        my @hits = grep /^$regex$/, @words;
        if ( @hits ) {
            print join( " ", $model, "matches", @hits, "using", $regex
+, "\n" );
        }
    }
}

__DATA__
lama
lamb
[download]