Depende do país específico, mesmo os países que fazem parte do espaço Schengen não harmonizaram sua política nessa área. Por exemplo, você pode fazer isso na Alemanha ( usando seu passaporte japonês ou australiano) ou no Países Baixos (somente para os australianos, os cidadãos japoneses não são cobertos lá), mas não na França. Na verdade, existe um programa Working Holiday Visa na França para cidadãos japoneses e australianos, para que você possa ficar lá também, mas é necessário para solicitar o visto certo de fora da França em um país onde você é considerado residente.
Eu realmente não conheço as regras para a Itália, mas este documento do consulado em Melbourne e esta página da embaixada em Wellington (as regras poderiam, em princípio, ser diferentes para os cidadãos da Nova Zelândia, mas suponho que refletem alguma política italiana geral) ambos sugerem que a inscrição antecipada é necessária também para esse país. Existem também restrições significativas quanto ao tipo e à quantidade de trabalho que você poderia fazer, por exemplo, ao programa holandês.
Observe que você ainda pode visitar a França e a Itália por algumas semanas no verão (seus passaportes permitem estadias curtas sem visto), depois ir para um país europeu onde você pode obter um WHV, trabalhar lá por algum tempo e depois voltar para a França ou em outro lugar no espaço Schengen para outra visita. Mas você não pode permanecer por um ano inteiro na França ou na Itália se não tiver organizado um VHC antes de sair da Austrália (ou onde quer que você reside agora). Consulte Faz visto de turista (90 dias) se aplica após um visto de longo prazo terminar em países Schengen?
Eu não estou 100% positivo sobre isso, mas pode até ser possível solicitar o WHV francês da Alemanha ou da Holanda se você estiver hospedado em outro WHV. Você simplesmente não pode fazer isso da França. Assim, primeiro você pode obter um WHV em um dos países mais fáceis para iniciar o processo e depois mudar para outros países europeus conforme necessário (além do esforço para descobrir as regras e completar a papelada, há taxas e atrasos para cada aplicação então isso só faz sentido se você pretende viajar pela Europa por mais tempo).