Cache $self->{S_KEY} instead of going after it fresh each time. Likewise, cache and maintain information about stuff you know, such as the key length. Once that's sorted out, it'll be easier to look for less expensive ways to do the individual shifting/appending operations.

sub Make_shiftedKey ($) {
    my $self  = shift;
    my $shift = shift;
    my $shiftIsOdd = $shift & 1;
    my $s_key = $self->{S_KEY};
    my $length_s_key = length $s_key;

    if ( $shiftIsOdd ) {
        $s_key = substr($s_key, 1);
    } else {
        # $s_key = substr($s_key, 0, $length_s_key) - 1);
        chop($s_key);
    }
    $len_s_key--;

    foreach ( 1 .. ($shift - 1) % $length_s_key ) {
    {
        # my $key = substr($s_key, 0, 1);
        # $s_key = substr($s_key, 1);
        # $s_key .= $key;

        $s_key =~ s/^(.)(.*)$/$2$1/;
    }

    $self->{S_KEY} = $s_key;
    return $s_key;
}
[download]

Unless I misunderstood or mistranslated your code, it leaves the key one character shorter. Is that what you intended?

Update: read the above as background, then skip directly to lemming's solution below.