In this example, having chosen to sort descending by count, you can take the opportunity to exit the loop as soon as the count drops. I couldn't find any additional tricks that ended up faster other than the fact that apart from that this code was as simply translated from the requirement as I could manage:

my @instances = qw (
                     AAAAA
                     ATCGA
                     ATAAA
                 );
my @instances2 = qw (
                     AAAAA
                     AACGA
                     ATAAA
                     ATAAA
                 );

for my $iref ( \@instances, \@instances2 ) {
    print Concensus( @$iref ) . "\n";
}

sub Concensus {
    my $result = '';
    my $length = length( $_[0] );
    for (my $i = 0; $i < $length; $i++ ) {
        my %count = ();
        for my $input ( @_ ) {
            $count{ substr( $input, $i, 1 ) }++
        }
        my $winners = '';
        my $wincount = 0;
        for my $try ( sort { $count{ $b } <=> $count{ $a } } keys %cou
+nt ) {
            if ( $wincount ) {
                ( $count{ $try } == $wincount )  or last;
            }
            else {
                $wincount = $count{ $try };
            }
            $winners .= $try;
        }
        ( length( $winners ) > 1 ) and $winners = "[$winners]";
        $result .= $winners;
    }
    return $result;
}
[download]