Your proposal is underspecified.  (And 'yours' is inconsistent with 'your';-). If you want sequential replacememt in multiple scans, make sequential replace calls.  Use a loop if the number of replacement scans is variable or large.  To be sure of the order of replacements, a sequence is better than a dict, but dict.values() instead would work in the following code.

s = 'this is my string'
for old, new in (('my', 'your'), ('string', 'car')):
    s = s.replace(old, new)
print(s)

If you want parallel replacement in a single scan, a different scanner is required.  If the keys (search strings) are all single letters, one should use str.translate.  For a general string to string mapping, use re.sub with a replacement function that does a lookup.

import re

s = 'this is my string'
subs = {'my': 'your', 'string': 'car'}
print(re.sub('|'.join(subs), lambda m: subs[m.group(0)], s))

In any case, the proposal to modify str.replace should be rejected.

However, the re code is not completely trivial (I did not work it out until now), so I think it plausible to add the following to the re module.

def replace(string, map):
    """Return a string with map keys replaced by their values.

    *string* is scanned once for non-overlapping occurrences of keys.
    """
    return sub('|'.join(map), lambda m: map[m.group(0)], string)

I would reference this in the str.translate entry for when keys are not restricted to letters.

If adding replace() is rejected, I would like an example added to the sub(pattern, function, string) examples.