Did Avalokiteśvara, Mañjuśrī, Samantabhadra, and Kṣitigarbha exist before Śākyamuni? In other words, did they exist first, and then Śākyamuni became a Buddha later on?
From a canonical perspective, Shakyamuni is one of many Buddhas (i.e. humans who attained satori) and many lived before him, so the answer would be yes.

According to Therevada, each Kalpa has 1.000 Buddhas. Theravada lists some of these as "the named Buddhas":


Vipassī (the 998th Buddha of the vyuhakalpa) 
Sikhī (the 999th Buddha of the vyuhakalpa) 
Vessabhū (the 1000th and final Buddha of the vyuhakalpa) 
Kakusandha (the first Buddha of the bhadrakalpa)
Koṇāgamana (the second Buddha of the bhadrakalpa) 
Kassapa (the third Buddha of the bhadrakalpa) 
Gautama (the fourth and present Buddha of the bhadrakalpa)


In Mahayana, Amithaba was originally a monk called Dharmakāra in very ancient times (long before Shakyamuni).

From a historical research perspective, the Mahayana deities first appear in scriptures hundreds of years after Gautama's lifetime.