A big bow drill using diamond-tipped bits would work.
Africa had diamonds, and the Sahara Desert used to have trees.
I watched a video last year in which a number of researchers were interviewing the owner of a stone cutting company at Giza in Egypt.
He examined some of the drill holes in the monument stones with an illuminated optical magnifier. He told the researchers that the holes were produced with a tool that rotated at higher rpms and greater pressures than any tools he's aware of.
You should have seen the look on that stone mason's face. He was honestly baffled at what he was looking at.