Michael wasn't sure of Fredo's betrayal. He only suspected. It wasn't until the Superman show that his worst fears were confirmed. That night, he was still reeling from the idea that his own brother had betrayed him. He certainly had no time to put a hit in place.

Additionally, I don't think that Michael really was going to kill Fredo until he realized the depth of his brother's jealousy when they were in the boathouse. Until that moment, I don't think he had a clue that his brother resented him to that extent. With that tirade, Fredo revealed his true self and sealed his fate.