Any ideas on how to use both directories at the same time?

Include directories (i.e. where the compiler looks for header files — in addition to the standard places) are specified via the -I option to gcc (multiple occurrences of -I are allowed).  So, the following perl Makefile.PL option should achieve the desired effect (untested, though):

--with-libidn-inc="libidn-1.9\lib -Ilibidn-1.9\win32\include"
[download]

Due to this snippet from Makefile.PL

GetOptions
(
        ...
        "with-libidn-inc=s" => \$incdir,
);
[download]

the value "libidn-1.9\lib -Ilibidn-1.9\win32\include" is being assigned to $incdir, which is then interpolated here

        $Params{INC} = "-I$incdir";
[download]

IOW, $Params{INC} now holds the two -I options, which in turn should end up in the appropriate places in the generated Makefile...

(In case that doesn't work, you might want to try specifying absolute paths to the include directories.)