The problem now is: How to go from %C3%A5 etc. to \xC3\xA5?

That's exactly what this line of code does:

  s/\%([0-9A-Z]{2})/chr(hex($1))/egi;
[download]

Did you try that? The left side matches any "%HH" pattern, and captures the two hex digits into $1; in the right side, "hex()" interprets $1 as a hex number, and "chr()" turns that value into a single-byte character. (Or it should, unless maybe you've put a "use utf8" somewhere above this line -- if that's the problem, put this regex into its own block with "use bytes":

{
   use bytes;
   s/\%([0-9A-Z]{2})/chr(hex($1))/egi;
}
[download]

As for your eval attempt, I think the first "$_" in "$_=$_" needs to have a backslash in front of the dollar-sign: "\$_ = $_". In any case, I would advise against changing every percent-sign into "\x" -- there might be some cases of "%" that are not followed by a pair of hex digits.

(update: Actually, in the context of dealing with uri strings, that last point is moot -- it surely must be the case in uri encoding that every "%" character is part of a "%HH" expression, and "%25" is used to express a literal percent-sign in the data. But the point is relevant for any data that might be a "defective" combination of uri encoding and plain text.)