Does that requirement strike anyone else as ironic?

From the POD for Switch: "Copyright (c) 1997-2008, Damian Conway. All Rights Reserved."

From the POD for Perl::Critic: "Most Policy modules are based on Damian Conway's book Perl Best Practices."

It's no surprise that Perl::Critic policies had to be violated to create Switch. Here are some of the obstacles you're going to encounter in finding a module that emulates given and when while at the same time not violating any of the Perl::Critic rules:

• Using subroutine prototypes violates Perl::Critic. Yet creating new syntax (as Switch does, and any other given/when emulation would probably have to do) almost always involves using prototypes.
• Switch disables strictures in some places. This violates Perl::Critic (though as has been mentioned in an earlier post, it's a silly rule). If there were another implementation of Switch under a different name (and different approach), it would probably need to do so somewhere in the code.
• Switch uses the one-argument form of bless to create some magic. Syntax emulation often requires such magic, so whether or not Switch is the solution, whatever solution is used may need to do this too. ...oh, and that violates Perl::Critic too. It's probably possible to accomplish this same magic using the two-arg version of bless, but putting already funky code through extra contortions to pass Perl::Critic isn't necessarily a good way to keep the bug count down.
• Whatever solution you find that doesn't violate any of the above, it will have to do so without also violating some other policy. I have my doubts as to whether that's possible given how difficult it is to cleanly add new syntax to Perl. (Even Try::Tiny violates two of the three policies mentioned above.)

And those are just the things that Perl::Critic complains about at "severity=5". As you approach greater severity it's going to get uglier fast. But most importantly, Switch isn't even "recommended" nowadays. It is a source filter. It has some serious limitations.

So what about alternatives? There really is no given/when emulation available for Perl 5.8.x that doesn't make compromises to achieve the magic. If the compromises are a deal-breaker (and they probably ought to be, really), you'll have to shift to a different tack.

App::perlbrew will assist you in installing a version of Perl that can co-exist with your system's Perl, and that doesn't require elevated privileges to install. If your constraint to v5.8.x is based on the limitations of what's installed on the system and what you have permission to install globally, perlbrew might help you to overcome those limitations.

On the other hand, if the limitation is that your client requires that you stick with 5.8.x, you may need to take a step back from the problem and examine other ways to achieve your goal. Perl existed for nearly 20 years without given/when, and its addition to Perl's syntax didn't suddenly make some hard things possible. It really only serves to make some things easier. But it's not the only tool that can be used to accomplish the same result. We don't know anything about the code you're contemplating, so we can't really comment on what pre-given/when syntax you should choose. But rest assured there is a solution to any problem that given/when solves, even without using given/when.

Looking for perlcritic safe modules...

LOL!