Você pode fazer:
sed 's/subtitle[0-9]\{1,3\}">/&<span style="style0">/'
Corresponde à legenda [0-200] ao combinar de 1 a 3 dígitos usando \{1,3\}
e substitui isso pelo padrão correspondente com <span style...
adicionado.
Se você inserir:
<p begin="540960420t" end="600189590t" xml:id="subtitle8">-Some text.<br/>-Some more text</p>
<p begin="601020420t" end="653572920t" xml:id="subtitle9">-Something else<br/>Some more text</p>
<p begin="654403750t" end="731560830t" xml:id="subtitle10">More words<br/>-more text</p>
<p begin="732401670t" end="786625840t" xml:id="subtitle11">Some text.<br/>Some more text</p>
Isto irá produzir
<p begin="540960420t" end="600189590t" xml:id="subtitle8"><span style="style0">-Some text.<br/>-Some more text</p>
<p begin="601020420t" end="653572920t" xml:id="subtitle9"><span style="style0">-Something else<br/>Some more text</p>
<p begin="654403750t" end="731560830t" xml:id="subtitle10"><span style="style0">More words<br/>-more text</p>
<p begin="732401670t" end="786625840t" xml:id="subtitle11"><span style="style0">Some text.<br/>Some more text</p>