It depends on what you're focusing. In the case of a bot trying to break a password by a brute-force attack, I consider the lapse to span from the first second the bot started its attack to the very second the password is broken. I don't consider the span to be the last try that breaks the password. And no, I don't consider evolution to have being looking for multicellularism and finally finding it. In the context of speculating about life in Ganymede (without falling for the fantasies of our fellow forum member Kathie Bondar), those eons are most likely necessary there to have a chance of developing complex life. The environment there doesn't promise a volume of activity and events together with a context showing enough stability yet enough change, for us to expect an evolutional speed faster than Earth's.
About the rest of your post, it seems to lump external influences -like volcanoes or nutrients- with not well defined internal changes -a new protein- as
a structural change. Of course, developing the biochemical paths that allow cell differentiation requires a lot of useful proteins to be "created" by random mutations. But it's enough to say that the structural changes from single-cell to multi-cell organisms were internal and them to be tried against a changing environment wasn't any surprise.
Like any innovation, multi-cellular organisms required a set of changes to be achieved together in their "inner workings". While getting there, partial changes had to be kept without compromising the survival of the individual organisms. So, like the brute-force robotic attack, eons passed while, yes, what can be regarded as trying in many directions, and at some point the "password was broken".
Multicellularism is arguably the most important innovation in the history of life on Earth. Even meiosis, with its final achievement, sexual reproduction, is less impressive
from a cold biological standpoint.
What I am willing to concede is that the enormous set of changes necessary to generate the structural leap into multi-cellularism is probably easier to achieve in a context of pretty stable environmental conditions, rather than the "all the bets are off" context of any sudden change like a volcano or a new nutrient. And in that matter Ganymede might have some advantage.