<PKEY> will only read one line from the file, or, in list context (as you have it there), read all lines as lists. Unless you have no line endings in your files, this is likely not what you want. I recommend reading the file into a variable first, inspecting the variable for correctness, and then passing on the variable to ->setPrivateKey.

Yay! With the code below it worked:

#!/usr/bin/perl
use Crypt::SMIME;

open(PKEY, "/home/alice/ssltestkey.pem") || die "open failed: $!";
open(CERT, "/home/alice/ssltestcert.pem") || die "open failed: $!";

my $plain = <<'EOF';
From: alice@example.org
To: bob@example.org
Subject: Crypt::SMIME test

his is a test mail. Please ignore...
EOF

my $privkey = do { local $/; <PKEY> };
my $crt = do { local $/; <CERT>};

my $smime = Crypt::SMIME->new();
$smime->setPrivateKey($privkey, $crt);
my $signed = $smime->sign($plain);
print $signed;
[download]

Thank you andal, Corion, sundialsvc4 for your suggestions!