I like blokhead's glob()-based solution. Here is one that is based on binary arithmetic (aka bit fiddling).

Essentially, filling in the dashes in a template amounts to counting upwards the bits indicated by dashes while keeping the other bits unchanged. For n dashes, this results in 2**n values. The subroutine increment_masked() below does one counting step arithmetically, given a value and a mask indicating the original position of dashes.

To expand a template of zeroes, ones, and dashes, extract from the template a mask (a number with 1-bits where dashes were, 0-bits otherwise), and a starting value (a number with zeroes where dashes were, other bits unchanged from the template). Apply increment_masked() appropriately to the starting value and collect the results. This is what the sub expand() does.

The final result is achieved by mapping expand() over the given templates.

my @data = qw( 000- 0101 011- 1-0- );
my @res = map expand( $_), @data;
print "@res\n";

sub expand {
    my $template = shift;
    my $n_dashes = $template =~ tr/-//;
    my $mask; # ones where - was, else 0
    ( $mask = $template) =~ tr/01-/001/;
    my $val; # zeroes where - was, else unchanged
    ( $val = $template) =~ tr/01-/010/;
    $_ = oct "0b$_" for $mask, $val;     # transform to numeric
    my @coll = $val;
    push @coll, $val = increment_masked( $val, $mask) for
        1 .. 2**$n_dashes - 1;
    @coll;
}

# Increment the combined unmasked bits as a single binary number,
# leaving masked bits alone. Masked bits are indicated by a 0-bit in
# the mask, unmasked bits by 1
sub increment_masked {
    my ( $x, $mask) = @_;
    
    (
        (   
            ($x | ~$mask) # fill masked bits with 1
            + 1           # increment (carry will jump over...
                          # masked stretches)
        ) 
        & $mask)          # clear masked bits, leaving...
                          # incremented bits alone
    | ($x & ~$mask);      # restore masked bits from $x
}
[download]

Anno

Update: Typos corrected
Much later update: Added comments to sub increment_masked()