Per my rough estimations the distances at which missile and gun projectiles arrive at exactly the same time is 5100m for the missile (with 5600m for thegun, as previously mentioned), so the missile can be launched up to one second later. Beyond that point the missile will arrive earlier. Beyond about 8000m range the missile will arrive so much later that the Fantom can't get a single shot off. In order to achieve five hits (with an accuracy of 80%) the Fantom needs half a second (assuming a single-barrel gun), which would mean a missile release at 7.5km range (~8.5 seconds missile flight time). This extreme scenario does however not make too much sense to me because the Russian pilot would probably bank immediately after missile release, which doesn't allow the gun to open fire at 5600m (to hit at its nominal max range of 4000m).

So, 5,100...7,500m range is covered by your artistic license, I'd say.
I'm a crappy engineer, though, and not a rocket scientist, so my estimations are to be treated with caution. They should however give you an impression of the distances involved. It should also make clear why in the 1950s engineers thought they could do away with guns; with reliable missiles the gun is pretty much outranged in most relevant scenarios.