all_critic_ok provides it's own plan, so by providing a plan before calling it, you plan twice in the situation where it works. Instead you should do something like this:

use Test::More;

eval "use Test::Perl::Critic";
if ( $@ ) {
    plan skip_all => "because Test::Perl::Critic required for these te
+sts";
} else {
    all_critic_ok();
}
[download]

Even if you get your code working, the skip isn't going to work correctly because you are only skipping 1 test, and all_critic_ok() is going to run 1 test for each file returned by all_perl_files().