Is there any evidence in the Roman catacombs that the Early Church had a devotion to the Virgin Mary? Is there any archeological evidence in the catacombs of Rome that the Early Church had any (particular) devotion to the Virgin Mary? If so, what are the sources that support such a devotion?
Not prior to the 2nd century, mainly since the catacombs were not developed until then. 

While there are various Christian frescos in these underground tombs which demonstrate a devotion to the saints, including the Virgin Mary, the time period for their origin would be no earlier than the late 2nd century or early 3rd, for even though Christians immediately began burying their dead in the catacombs after they became available, they did not become regularly used for worship until persecution forced them underground. The frescos did not come till later, and those that are dated are probably from the late 3rd or early 4th century. By 380 A.D., the catacombs were no longer used for meeting as Christianity became legal in that year. 

So even the earliest frescos would reflect practices removed by at least a century from Christ. Yet, with other historical records it is clear that devotion to the saints, including Mary, was obviously early and seems to have developed parallel with the use of the catacombs to bury the early martyrs.

Whatever the case, since the catacombs yield little empirically of the Church prior to the 2nd century and since devotion to saints seems to be of the era of the catacombs' first use by Christians, nothing found in these tombs can guarantee a connection with the Church in its most primitive and primary state.