W roku 1998 Wołodymyr Kuźmenko wystąpił w roli Turiddu („Rycerskość wieśniacza”), którą zadebiutował w Danii. W tym samym roku po raz pierwszy zaśpiewał rolę Hermana („Dama pikowa”) w Wielkiej Brytanii, która miała stać się jedną z jego najwybitniejszych kreacji. Natychmiast zaproszono go do wykonania tej partii w nowej produkcji „Damy pikowej” w Stuttgarcie oraz do roli Radamesa („Aida”) w nowej produkcji w Scottish Opera. Kolejnym sukcesem okazał się jego debiut jako Radames w Dresden Opera. Podczas prób w Stuttgarcie zaproponowano mu kontrakt w Württemburgisches Staatstheater, gdzie śpiewał m.in. Cavaradossiego, Kalafa („Turandot”) oraz tytułową rolę w „Don Carlosie”. W roku 2000 Wołodymyr Kuźmenko zadebiutował w Opernhaus Zurich rolą Hermana. Tę samą partię wykonywał w Bayerische Staatsoper w Monachium w kwietniu 2001 roku na Munich Opera Festival. W sezonie 2001/2 Kuźmenko śpiewał we wznowieniach „Toski” i „Don Carlosa” w oraz w nowej produkcji „Trubadura” w Stuttgarcie. Kontynuował swą współpracę z Bayerische Staatsoper w roli Hermana. W Hiszpanii debiutował rolą Herman, którą wykonał na deskach Teatre Liceu w Barcelonie w zastępstwie za Plácido Domingo w roku 2003.