Wouldn't there be a "grand plus" coalition in that case, with FDP or Greens recruited to plug the gap? Although if those two don't make it given their weakness in East Germany, that would mean a pretty mad choice.
Actually yeah, an extended grand coalition would work in all of those cases:
Brandenburg: Either CDU+SPD+Greens or CDU+FDP+SPD would get a majority
Sachsen: The Greens only got 4.6% so they would theoretically be out. As for the remaining, CDU+SPD+FDP would just barely get a working majority (45.6% compared to 43.1% for AfD+Linke). Though considering CDU only got 26.9% (didn't even come first) and SPD got barely more than 10% this doesn't really qualify as a grand coalition anymore
Thüringen: Again, the greens only got 3.6% so they would theoretically be out. This means that a regular grand coalition would actually have a very narrow majority (46.2% for CDU+SPD vs 45.6% for everyone else except the greens).