It is generally believed that Shakespeare based Macbeth on Raphael Holinshed's Chronicles of England, Scotland and Ireland, Volume 5 (1587). This is not just because Shakespeare's version of the story closely follows Holinshed's, but because Shakespeare consistently uses Holinshed's phrases and repeats his mistakes. For example, Holinshed describes the encounter with the three witches thus:
It fortuned as Macbeth and Banquo journeyed towards Forres, where the king then lay, they went sporting by the way together without other company, save only themselves, passing thorough the woods and fields, when suddenly in the midst of a land, there met them three women in strange and wild apparel, resembling creatures of elder world, whom when they attentively beheld, wondering much at the sight, the first of them spake and said, "All hail Macbeth, thane of Glamis" (for he had lately entered into that dignity and office by the death of his father Sinel). The second of them said, "Hail Macbeth thane of Cawder." But the third said, "All hail Macbeth that hereafter shalt be king of Scotland."
(I've modernized the spelling in this and other extracts from Holinshed.)
Macbeth not only has essentially the same dialogue as this passage:
All hail, Macbeth! hail to thee, thane of Glamis!
All hail, Macbeth, hail to thee, thane of Cawdor!
All hail, Macbeth, thou shalt be king hereafter!
but also repeats the mistake about Macbeth's father:
Stay, you imperfect speakers, tell me more:
By Sinel's death I know I am thane of Glamis;
Macbeth's father was actually Findláech mac Ruaidrí (Finlay of Moray).
Holinshed describes the prophecy and the Macbeth's death as follows:
And surely hereupon had he put Macduff to death, but that a certain witch, whom he had in great trust, had told that he should never be slain with man born of any woman, nor vanquished till the wood of Birnam came to the castle of Dunsinane. By this prophesy Macbeth put all fear out of his heart, supposing he might do what he would, without any fear to be punished for the same, for by the one prophesy he believed it was impossible for any man to vanquish him, and by the other impossible to slay him. This vain hope caused him to do many outrageous things, to the grievous oppression of his subjects. At length Macduff, to avoid peril of life, purposed with himself to pass into England, to procure Malcolm Canmore to claim the crown of Scotland. […]
But after that Macbeth perceived his enemies' power to increase, by such aid as came to them forth of England with his adversary Malcolm, he recoiled back into Fife, there purposing to abide in camp fortified, at the castle of Dunsinane, and to fight with his enemies, if they meant to pursue him; howbeit some of his friends advised him, that it should be best for him, either to make some agreement with Malcolm, or else to flee with all speed into the Isles, and to take his treasure with him, to the end he might wage sundry great princes of the realm to take his part, & retain strangers, in whom he might better trust than in his own subjects, which stole daily from him: but he had such confidence in his prophesies, that he believed he should never be vanquished, till Birnam wood were brought to Dunsinane; nor yet to be slain with any man, that should be or was born of any woman.
Malcolm following hastily after Macbeth, came the night before the battle unto Birnam wood, and when his army had rested a while there to refresh them, he commanded every man to get a bough of some tree or other of that wood in his hand, as big as he might bear, and to march forth therewith in such wise, that on the next morrow they might come closely and without sight in this manner within view of his enemies. On the morrow when Macbeth beheld them coming in this sort, he first marvelled what the matter meant, but in the end remembered himself that the prophesy which he had heard long before that time, of the coming of Birnam wood to Dunsinane castle, was likely to be now fulfilled. Nevertheless, he brought his men in order of battle, and exhorted them to do valiantly, howbeit his enemies had scarcely cast from them their boughs, when Macbeth perceiving their numbers, betook him straight to flight, whom Macduff pursued with great hatred even till he came unto Lumphanan, where Macbeth perceiving that Macduff was hard at his back, leapt beside his horse, saying, "Thou traitor, what meaneth it that thou shouldst thus in vain follow me that am not appointed to be slain by any creature that is born of a woman, come on therefore, and receive thy reward which thou hast deserved for thy pains," and therewithall he lifted up his sword thinking to have slain him.
But Macduff quickly avoiding from his horse, yet he came at him, answered (with his naked sword in his hand) saying: "It is true Macbeth, and now shall thine insatiable cruelty have an end, for I am even he that thy wizards have told thee of, who was never born of my mother, but ripped out of her womb:" therewithall he stepped unto him, and slew him in the place. Then cutting his head from his shoulders, he set it upon a pole, and brought it unto Malcolm. This was the end of Macbeth, after he had reigned 17 years over the Scottishmen.
Given how closely this corresponds to Shakespeare's version of the story, this seems to put paid to the hypothesis that Shakespeare got it from Magnus. Nonetheless, we might ask the question about Holinshed. Did Holinshed get the story from Magnus?
Holinshed's source is thought to have been Hector Boece's Historia Gentis Scotorum (1527). The coming of Birnam Wood to Dunsinane is described in XII.25–6:
[…] mox ad novum castellum Dounsinnam castra ponit, certum animo atque constitutum habens hostes illic opperiri, nam turpe ducebat, nullo experto certamine, regno exire. […]
which is, in Dana F. Sutton's translation:
Soon he [Macbeth] encamped at Dunsany, having made up his mind to await his enemy there. For he thought it would be a disgrace to quit the throne without having fought a battle. But some of his friends urged him either to make peace with Malcolm on acceptable conditions, or to take the royal treasury and beat a retreat to the Hebrides, where he could hire mercenaries more reliable than the men who were draining away from him every day. But the Fates hurried the man onwards, for he was convinced that he was unconquerable until Birnam Wood had been brought there, so that death was not threatening him, since the soothsayers had predicted that he was not going to be killed by a man born of woman.
Malcolm followed Macbeth as quickly as he could, and on the day before he gained his victory he and his army halted next to Birnam Wood. When they had rested a while and attended to their bodily needs, he ordered them all to go into the forest, and for each man to cut of as large a branch as he could carry. Then he began his march during the first watch of the night. Crossing the Tay, at dawn they came in sight of their enemies, holding up their branches. When Macbeth saw this, he was frightened by the strange sight, thinking this was an ill omen for himself and his destiny.
You'll see that this is essentially identical to Holinshed's version, and again, this rules out the hypothesis that Holinshed got the story from Magnus. The first edition of Boece's Historia Gentis Scotorum (1527) precedes Magnus's Historia de Gentibus Septentrionalibus (1555), so the former can't be derived from the latter.
Boece gives his source for the early history of Scotland as:
[Richard] Vairement [fl. 1260s], a Spaniard who became Archdeacon of St. Andrews, [who] chronicled the events of our nation from its inception down to the reign of Malcolm III Canmore
Unfortunately Vairement's chronicle has been lost, so we can't trace the story any further. But it is certainly possible that the Scottish and Danish versions of the legend ultimately derive from a common source. In Vairement's day the Western Isles were still (at least nominally) ruled by Norway and it would not be surprising if legends were transmitted from Scotland to Scandinavia or vice versa.