Was there a Jewish belief prior to 30CE that a prophet other than Elijah would appear along with the Messiah?
If so, what evidence is there for it, what were the details of this belief, what documents is/was it in, and who believed it?
The question seeks evidence from 30CE or earlier and not later.
There was a belief in some circles of multiple types of messiah. The community living in Qumran make reference to the coming of נביא ומשיחי אהרון וישראל, "the prophet and the messiahs of Aaron and Israel" (Community Rule/1QS, column 9 line 11).
The article "The Endtime Return of Elijah and Moses at Qumran" argues for Moses (or a prophet in the role of Moses) being the prophet expected to come with the Messiah at Qumran, the source for the belief probably being Deuteronomy 18:15, which promises a prophet "like me" (Moses), and may have been interpreted messianically. Elijah would have been the priest-type "Messiah of Aaron."
This was the belief of the community at Qumran shortly before the destruction of the Second Temple. They are often compared with Essenes and/or followers of John the Baptist, but identifying those groups with each other is controversial. Similar, though not identical, beliefs about multiple messiahs existed in the Second Temple period, as in the apocryphal Testament of the Twelve Tribes (citations to similar passages can be found in this article).
