A poco que tu HTML sea un poco complejo, ningún módulo de Perl que haga el trabajo él mismo te va a dar un buen resultado.
Para obtener un buen resultado lo que necesitas es dejar que tu navegador se encargue del
renderizado... yo investigaría cómo puedo automatizar el Internet Explorer con
Win32::OLE para que cargue el reporte y lo mande a imprimir a una impresora PDF.
Con Firefox (o el xul-runner que lleva por debajo en realidad) también podrías programar una aplicación en JavaScript que hiciese lo mismo... puede que en este caso incluso no sea necesario abrir una ventana si no que puedas hacerlo todo en
batch.
Por último, también puedes importar el HTML en el Office o en OpenOffice.org a ver qué tal lo convierte a su propio formato y de nuevo usar Win32::OLE para automatizar el proceso. De todas formas aquí va a pasar lo mismo que con los módulos Perl, el resultado probablemente no sea muy bueno visualmente.