Não há necessidade de converter o arquivo de legenda. Tente isto:
abra o VLC, vá para Tools > Preferences > Subtitles & OSD
e sob defualt encoding
altere a codificação para Eastern European (Windows 1250)
(você disse que tentou algumas combinações, mas não sei quais)