multi-recursive replacement function
You are using the Map more like a list...

EDIT: this is NOT working:

You could create an object to hold one translation ({X => {"cake","egg"}) then instead of all the Maps you could use a List (of those translations) and always remove and use the first element and pass the shorter list to the next call of your method.

EDIT: this IS working:

You could use a List with the translation and add an index parameter in you method to know which element from the list use. Then you increment the index once before making the recursive calls...

Here is some code (without constructors getters etc...):

public class Translations {
    final String key;
    final Set&lt;String&gt; translations;
}


public static void addAllReplacements_2 (String source,List&lt;Translations&gt; translationsList, final int index, Set&lt;String&gt; targets) {
    if (index == (translationsList.size())) {
        // no more replacements:
        targets.add(source);
    } else {
        // pick an entry
        Translations translations = translationsList.get(index);
        String text = translations.getKey();
        Set&lt;String&gt; translationValues = translations.getTranslations();

        final int nextIndex = index+1;

        for (String translationValue: translationValues) {
            addAllReplacements_2(
                    source.replace(text, translationValue),
                    translationsList,nextIndex,
                    targets);
        }

    }
}