When did the ancient Egyptians start burning mud to produce clay..

… in order to use it as a building material?

Appearance of mud brick seems to be in the late pre-dynastic phase, around 3500-3150 BC-- they had pottery before that, though. The first bigger mastabas in the 1st dynasty (around 3100 BC; eg. Queen Merneith’s at Saqqara) seem to have still been brick.
But I’m sure brick was used much earlier than that somewhere. . . I assume Jericho was brick, for example.