If I understand you right, Win32::Job won't help me in this case.

Actually, it probably will. According to the docs:

By default, processes created using CreateProcess by a process associated with a job are associated with the job;

Which mean if you create a job (a Win32::Job), and then associate the top level process you start with that job, then any processes it spawns will also be associated with that job. You should then be able to kill them all by killing the job.