Make 2 movies. Split the cast in two - Spock, Kirk, Uhura and Kirk's dad in the first one. Bones, Sulu, Chapel and Scotty in the second one, and have each movie take place during the same time but in alternating locations.
The first movie could feature the entire csst in the opening scene before they diverge, and the second movie can do the same with the final scene.
That way, you can pay the entire cast what you would pay them for one movie, but get two out of it. And you only have to pay for one set of sets.
Film them both at the same time so they can share other resources too.
And since the star power is diminished in the 2nd movie, add a TNG character to it, like Data.