Dr. Dan Gazit wrote (in Hebrew) that the Magen David is one of the variations on the motive of the rose, which was prevalent right after the invention of the pair of compasses. There are no such roses on the Nabateans' ceramics because they used free hand and not compasses for making them.
I think when Dr. Dan Gazit says Magen David he means Hexagram. Uri Ofir claims that the origin of the Jewish Magen David is from the Tabernacle, but that doesn't imply that there weren't hexagrams before that.
According to Greek mythology Perdix, the nephew of Didalus, invented the first pair of compasses. Anyhow compasses seem to be here since immemorial time, and it's hard to pinpoint the date people started to use them, as well as it’s hard to trace back the first Hexagram.