Unless you need some of those variables later, we could eliminate some clutter.

use strict;
use warnings;

#generate all posibilites of a DNA sequence
my @Bases = qw(A C G T);
my $SequenceMinLength = 1;
my $SequenceMaxLength = 3;
print 'Number of Sequence lengths to permute is ',
      $SequenceMaxLength - $SequenceMinLength + 1, "\n";

my @allSequence;
foreach my $currLength ($SequenceMinLength .. $SequenceMaxLength){
    push @allSequence, Ordered_Combinations($currLength, @Bases);
}

#Prints sequences to screen
# - Too many entries after length of sequence is greater than 4.
my $i;
foreach my $finalsequence (@allSequence){
    ++$i % @Bases ? print "$finalsequence\t" : print "$finalsequence\n
+";
}
[download]

By using @Bases instead of 4, we get @Base columns, aiding readability.

sub Ordered_Combinations {
    my $n = shift;
    --$n ? map {
             my $d = $_;
             map "$d$_", Ordered_Combinations($n,@_)
               } @_
         : @_
}
[download]

HTH,
Charles K. Clarkson