I think it was being kicked around since just after Don Corleone was shot. There is a scene where Clemenza, Tessio, Sonny, Tom and Mike are sitting around and everyone is talking all at once. If you listen carefully you hear Clemenza reading names from a written list; he says:
"That's a lot of bad blood; Solozzo, Phillip Tataglia, Bruno Tataglia, Carbone ..."
to which Mike responds: "are you gonna kill all those guys?"
(Sonny then says "Mikey, keep out of this")

Though Mike is not "devising" the plan at that time, he does become aware of the possabilities.

That might be the earliest that any such plan is discussed.