Well the POD is the Mithridatic Wars. Having Tigranes take over Palestine isn't that hard since the area fell into civil war shortly after the POD IIRC. Ptolemaic Egypt is practically a client state of Rome in everything but name as it was OTL. The Arverni came close at times to uniting the Gallic tribes. Dacia was strong and united during Burebista around this time or shortly after the POD.
Mithridates had taken over all of Asia Minor at one point as well.
The problem is that while you could probably have something like Tigranes taking over Palestine, that doesn't mean it could lead to a lasting Armenian Empire from Armenia proper to Palestine.
That's going to be the tricky part - having this as a map of the situation in (say) 60 BC, but I'm not sure those empires could last with an ambitious Rome. Or Persia - more so for Armenia than the Pontic state.
Gaul being united is something I don't know enough about to observe how well it would work, but Rome is likely to try to disrupt that.