I started out thinking I would point out style and other issues with your code item by item, but instead I've essentially rewritten it rather than try to fix a whole series of (mostly small) issues.

The key problem with your decrypt is that it is "indexing the wrong way round" so in effect it re-encrypts the encrypted text instead of decrypting it.

I've changed the structure of the code so that it is clear that the encryption is block based so instead of breaking the plain text into characters, it breaks it into key length blocks and deals with those.

#!user/bin/perl
use warnings;
use strict;

my $plainTextIn = <<EOF;
abcdefghijklmnopqrs1234567890
EOF
my $keyTextIn = <<EOF;
secretmachine
EOF

test('testing');

sub test {
    my ($testing) = @_;
    open my $plainIn, "<", \$plainTextIn;

    my $plainText = <$plainIn>;
    chomp $plainText;
    close $plainIn;

    open my $keyIn, "<", \$keyTextIn;
    my $key = to26(<$keyIn>, $testing);
    close $keyIn;

    my $cipherText = encrypt($key, $plainText, $testing);
    print ">>>>>>>>>>>>>\n" if $testing;
    my $decryptText = decrypt($key, $cipherText, $testing);

    print <<TEXT
$plainText
-----------
$cipherText
-----------
$decryptText
TEXT
}


sub encrypt {
    my ($key, $plainText, $testing) = @_;
    my $keylength  = length ($key);
    my @blocks     = $plainText =~ /(.{1,$keylength})/g;
    my $matrixSize = @blocks * $keylength;

    print "-- Length of key: $keylength --- Key: '$key'\n" if $testing
+;
    print "-- Plain text: '$plainText'\n"                  if $testing
+;

    my @permut = calcPermut($key);

    print "-- Permutation: @permut\n"         if $testing;
    print "-- Size of tableau: $matrixSize\n" if $testing;

    $blocks[-1] .= '0' x ($keylength - length $blocks[-1]);   # 0 pad 
+last block

    for my $line (@blocks) {
        print "-- '$line'\n" if $testing;
        $line = join '', map {substr $line, $permut[$_], 1} 0 .. $keyl
+ength - 1;
    }

    return join '', @blocks;
}


sub decrypt {
    my ($key, $cipherText, $testing) = @_;
    my $keylength  = length ($key);
    my @blocks     = $cipherText =~ /(.{1,$keylength})/g;
    my $matrixSize = @blocks * $keylength;

    print "-- Length of key: $keylength --- Key: '$key'\n" if $testing
+;
    print "-- Cipher text: '$cipherText'\n"                if $testing
+;

    my @permut = calcPermut($key);

    print "-- Permutation: @permut\n"         if $testing;
    print "-- Size of tableau: $matrixSize\n" if $testing;

    for my $line (@blocks) {
        my @newLine;
        print "-- '$line'\n" if $testing;
        $newLine[$permut[$_]] = substr $line, 0, 1, '' for 0 .. $#perm
+ut;
        $line = join '', @newLine;
    }

    return join '', @blocks;
}


sub to26 {
    my ($mytext, $testing) = @_;    # Get input string.
    chomp $mytext;
    print "-- to26:'$mytext'\n" if $testing;
    $mytext =~ s/0/zero/g;          # Numbers to verbal description.
    $mytext =~ s/1/um/g;
    $mytext =~ s/2/dois/g;
    $mytext =~ s/3/tres/g;
    $mytext =~ s/4/quatro/g;
    $mytext =~ s/5/cinco/g;
    $mytext =~ s/6/seis/g;
    $mytext =~ s/7/sete/g;
    $mytext =~ s/8/oito/g;
    $mytext =~ s/9/nove/g;
    return $mytext;
}


sub calcPermut {
    my ($key) = @_;
    my @keylist = split //, $key;
    my @permut;

    $permut[0] = 0;
    for my $i (1 .. @keylist - 1) {
        my $j = 0;

        while (1) {
            if (($j >= $i) || ($keylist[$i] lt $keylist[$permut[$j]]))
+ {
                splice (@permut, $j, 0, $i);    # Insert $i at positio
+n $j
                last;
            }

            $j++;
        }
    }

    return @permut;
}
[download]

Prints:

-- to26:'secretmachine'
-- Length of key: 13 --- Key: 'secretmachine'
-- Plain text: 'abcdefghijklmnopqrs1234567890'
-- Permutation: 7 2 8 1 4 12 9 10 6 11 3 0 5
-- Size of tableau: 39
-- 'abcdefghijklm'
-- 'nopqrs1234567'
-- '8900000000000'
>>>>>>>>>>>>>
-- Length of key: 13 --- Key: 'secretmachine'
-- Cipher text: 'hcibemjkgldaf2p3or74516qns0009000000080'
-- Permutation: 7 2 8 1 4 12 9 10 6 11 3 0 5
-- Size of tableau: 39
-- 'hcibemjkgldaf'
-- '2p3or74516qns'
-- '0009000000080'
abcdefghijklmnopqrs1234567890
-----------
hcibemjkgldaf2p3or74516qns0009000000080
-----------
abcdefghijklmnopqrs12345678900000000000
[download]

Update: removed unused sub show