Bem, te recomendo a fazer pelo Nero normal mesmo.
Pois pelo Express, acho que ele vai tentar reencodar seu kvcd para coloca-lo dentro do padrão do VCD. E acho que não é isso que você quer.
E pelo nero normal, é quase o mesmo sistema para criar os menus. É só você abri-lo, selecionar a opção VCD, mto importante você desmarcar a opção "Create Standard Compliant Cd" ou seja, criar um VCD dentro dos padrões. Depois você clica na orelha menu, e faz o menu à seu gosto. Depois que terminar, é só clicar em "New" arrastar seu video para a janela do VCD, e mandar vêr. Qualquer dúvida é só postar.