will produce the following combinations from the string 'convert perl to-python'

Assuming you typoed:

#! perl -slw
use strict;
use Algorithm::Combinatorics qw[ variations_with_repetition ];

sub zip {
    my( $r1, $r2 ) = @_;
    my $n = @$r1 > @$r2 ? $#{$r1} : $#{$r2};
    map{ ( $r1->[ $_ ] // '', $r2->[ $_ ] // '' ) } 0 .. $n;
}

sub dashedCombos {
    my @words = split ' ', shift;

    map { join '', zip( \@words, $_ ) } variations_with_repetition( [ 
+' ', '-' ], $#words );
}

print for dashedCombos( 'convert perl to python' );

__END__
C:\test>1137970
convert perl to python
convert perl to-python
convert perl-to python
convert perl-to-python
convert-perl to python
convert-perl to-python
convert-perl-to python
convert-perl-to-python
[download]

  DB<123> $input="one two three"
 => "one two three"

  DB<124> $globber= join q|{' ','-'}| , split / +/, $input
 => "one{' ','-'}two{' ','-'}three"

  DB<125> print "$_\n" while glob($globber)
one two three
one two-three
one-two three
one-two-three
[download]

please note that line 125 acts as an iterator looping over all results, like yield permits.

for a flat list result just don't call glob in scalar context:

  DB<127> print join "\n", glob($globber)
one two three
one two-three
one-two three
one-two-three
[download]

update

just in case $input includes any meta characters or wildcards, you'll need to escape them before.

The following python code enables me to take a string of words and replace spaces with hyphens in every possible combination:

The number of every possible combination in the string "convert perl to python" are 8, not 5, or am I missing something?

my $str = 'convert perl-to python';
my $bits =()= $str =~ /[ -]/g;

for (0 .. (1<<$bits)-1) {
    my @l = split//,unpack'b*',pack'C,',$_;
    (my $out = $str) =~ s/[ -]/(' ','-')[shift @l]/ge;
    print $out, $/;
}
__END__
convert perl to python
convert-perl to python
convert perl-to python
convert-perl-to python
convert perl to-python
convert-perl to-python
convert perl-to-python
convert-perl-to-python
[download]

You get more off that if you use the string "don't convert perl to python" which gives you 16 combinations.

Update: I just noticed the OP wants to vary separators not words, so I'll address that further down...

my @superset = split /\s+/, 'convert python to perl';
my $N = scalar @superset;
for my $combo (0..((2**$N) - 1)) {   # a combo is also a bit mask
    print "selection:";
    for my $selector (0..($N-1)) {  # a selector is also a bit
    (2**$selector) & $combo and print ' ' . $superset[$selector];
    }
    print "\n";
}
[download]

selection:
selection: convert
selection: python
selection: convert python
selection: to
selection: convert to
selection: python to
selection: convert python to
selection: perl
selection: convert perl
selection: python perl
selection: convert python perl
selection: to perl
selection: convert to perl
selection: python to perl
selection: convert python to perl
[download]

Update: to vary spaces and hyphens (what I now understand is wanted), the same technique can apply

my @superset = split /\s+/, 'convert python to perl';
my $N = $#superset; # one less element than in the previous example
for my $combo (0..((2**$N) - 1)) { # a combo is a bit mask
    for my $selector (0..$N) {  # a selector is also a bit position
        print $superset[$selector];
        if ($selector == $N) {
            print "\n";
        next;
        }
    if ((2**$selector) & $combo) {
            print ' ';
        }
        else {
            print '-';
        }
    }
}
[download]

convert-python-to-perl
convert python-to-perl
convert-python to-perl
convert python to-perl
convert-python-to perl
convert python-to perl
convert-python to perl
convert python to perl
[download]

More update: Afterthought: 1 << $var is likely to be faster than, while being equivalent to:  2 ** $var.

Then you will need to construct an iterator.

Not sure what your list comprehension does, its hard to read.