I haven't drunken a lot of REST Kool-Aid, but i know enough to know that REST != CGI. REST isn't a subset or a superset of CGI for that matter. They are largely orthogonal concepts, overlapping only in as much as they both use HTTP for transport.

Note in particular that RFC 3875 specifically identifies only 3 valid HTTP Methods for CGI (HEAD, GET, and POST). Quite simply: if a CGI related Perl module is moderately useful for writing REST resources, that's a perk above and beyond the scope of it's primary function as a CGI library. Complaining that it doesn't support everything you need to implement a REST resource is like complaining that an XML Parsing module doesn't support everything you need to parse crufty HTML found in the wild.

Have you perchance considered using REST::Resource or REST::Application?