I agree that using Switch is a bad idea. And unfortunately, PPI and Perl-Critic don't yet understand the given/when syntax of Perl 5.10.
As for complexity scores, the general idea is to count the number of possible paths through the code. Perl-Critic approximates the McCabe score by adding one point for each logical operator (&&, ||, and, or, etc.) and each "if", "elsif", "while", "until", "unless", "for", and "foreach" keyword. When we add support for the given/when syntax, each "when" clause will also add one point.
So converting a long if/elsif/elsif chain into a given/when structure doesn't help your complexity score. Neither does consolidating nested "if" conditions with && and || operators. The best way to reduce complexity is to use dispatch tables as others have suggested, or to extract parts of the code into other subroutines.