Golfing Python string literals
Python 3, 264 262 bytes



f=lambda s,b='\\',r=str.replace:min(sum([['r'+d+s+d,d+r(r(s[:-1],b,b+b),d,d[1:]+b+d[0])+b*(s[-1:]in[b,d[0]])+s[-1:]+d][d in r(r(s+d[1:],b+b,'x'),b+d[0],b)or r(s,b+b,'')[-1:]==b:]for d in["'",'"',"'''",'"""']],[f(s[:k])+f(s[k:])for k in range(1,len(s))]),key=len)


Try it online!

This works but is very slow without memoization, which you can add with

import functools
f=functools.lru_cache(None)(f)


It found an improved solution for one of the test cases:

t"e"s"t"s"t"r"i"n"g"\'\'\'\'\'\'\'\
 -&gt; 't"e"s"t"s"t"r"i"n"g"'r"\'\'\'\'\'\'\'"'\\'
 -&gt; r't"e"s"t"s"t"r"i"n"g"\'\'\'\'\'\'\'''\\'


Previous versions of this answer returned incorrect results on the following, which could be added as test cases:

\\'"\\'\
 -&gt; "\\\\'\"\\\\'\\"
''"""''"""''
 -&gt; '''''"""''"""'\''''