There's a pretty easy trick to nested comprehensions.
Just write the loop as normal:
for name, values in map_of_values.items():
for value in values:
yield name, value
Then concatenate everything on one line:
[for name, values in map_of_values.items(): for value in values: yield name, value]
Then move the yield to the very start, wrap it in parentheses (if necessary), and remove colons:
[(name, value) for name, values in map_of_values.items() for value in values]
And that's your comprehension.
Maybe this makes more sense if you're reading it on a wide screen:
[ for name, values in map_of_values.items(): for value in values: yield name, value]
^^^^^^^^^^^^^^^^^
/------------------------------------------------------------------------------/
vvvvvvvvvvvvv
[(name, value) for name, values in map_of_values.items() for value in values ]