I'm going to get a little more radical and suggest that while Macbeth may have been anoutwardly loyal subject, he had the makings of a "king-killer" pretty close to the surface from the beginning.
While the witches may have been an instigation to Macbeth's actions, no mere words could make him commit the heinous acts he committed unless there was already something that evil lurking in his heart. The mere suggestion is not enough. Undoubtedly he already had that ambition in him, just waiting for an opportunity to present itself.
Too often Lady Macbeth is blamed for his actions, yet it's clear he has thoughts of murder before he ever sees her to discuss the predictions in person. Immediately after the witches disappear, Macbeth says, in an aside: "My thought, whose murder yet is but fantastical, shakes so my single state." He has barely had the prediction spoken to him and already the words "thought" and "murder" are in his mind.
Macbeth is not averse to violence to achieve a goal. He is a fighter, after all, and he is a vicious soldier. We see him in battle as he "unseam'd" his opponent "from nave to chaps."
The concept that two others (Malcolm and Donalbain, the King's sons) stand between him and even the possibility of the throne doesn't seem to enter his mind. In Act I scene 3 he says, If chance will have me king, why, chance may crown me, without my stir." One short scene later he is present when the Duncan names his oldest son Prince of Cumberland, successor to the throne; then he says, "Prince of Cumberland! That is a step on which I must fall down, or else o'erleap, for in my way it lies." His latent ambition has turned to a hunger for the throne in a very short time--even without his wife's promptings.
It's clear that Macbeth is a man who has ambitions to become king--and he quickly determines his general course of action and then carries it out. Not surprisingly, the result of those actions is paranoia and eventual death.
There are quite a lot of factors as for why Macbeth shows this change.
The witches are one reason.
Macbeth is initially proud of his position as the Thame of Glamis untill he is stirred by the witches' prophecies. They claim that Macbeth will become Thame of Cawdor and be King hereafter. After hearing such claims Macbeth finds out King Duncan had named him Thane of Cawdor, hence stopping at nothing to gain position as King of Scotland just as the prophecies foretold.
Lady Macbeth is another reason.
Lady Macbeth pushes Macbeth who wants the prophecy to come true. Macbeth initially lacks the enthusiasm as Lady Macbeth to commit the murder, but Lady Macbeth urges Macbeth to act on his desires or he will later think of himself as a fool and a coward.