You're quite right, Teribus, Hitler should have put those priorities the other way around. He should also have gotten the idea to invade Malta a whole lot sooner than he did. Time is always of the essence in such matters.

The Germans did succeed in taking the island of Crete...a similar proposition to taking Malta...and across a similar stretch of water...but it was a much bigger island than Malta. It cost their paratroopers dearly, but they took it. I believe they could also have taken Malta, with a combination of paratroops and seaborne assault, but specially the seaborne assault. They just had to do it soon enough, and with sufficient resolve, that's all.

It was foolish (or at least impractical) of them to attempt to successfully conclude a North African campaign without taking Malta...although...Rommel came close to pulling it off, even as it was.