Eu provavelmente usaria o FFmpeg para isso.
Se você deseja migrar as legendas como um fluxo separado em um formato de contêiner, você teria que usar o MKV:
ffmpeg -i input.mp4 -i input.sub -c copy output.mkv
Isso não funcionará no PS3, que não suporta MP4 (e o MP4 não suporta legendas DVB).
Se você quiser gravar as legendas no vídeo (para que elas não possam ser desativadas), você pode usar o filtro de vídeo de legendas do ffmpeg (será necessária uma compilação muito recente do ffmpeg):
ffmpeg -i input.mp4 -filter:v subtitles=input.sub -c:a copy -c:v libx264 -crf 22 -preset veryfast output.mp4