I don't foresee myself ever building a terror star, but i can offer the following plausible solution.

plan in advance where you want to strike, then design constructors to have the range and speed to arrived to that destination within a turn, also have the max logistics capabilities researched. ALso, count how many total constructors that is need to build a terror star from start to finish.

Instead of building a terror star from a destination afar, have the constructors all arrived in a fleet fomration to the destination, then start building the terror star in one turn, of course, guard those fleet(s) of constructor with other ships. I think this is the only way to resolve your movement problem.

Is is better to have a death star than to have a terror star.

I built terror stars for the first time yesterday. I admit I built them simply because I could. My impression was, it was really awesome to see the devistation, but very little more.

I will comment, related to the OP, that I was playing a game where all planets within a certain range got converted to 9+ quality planets, so invading all of my opponent's planets would have been quite an undertaking. So I destroyed 4 star systems (all with 4 or more populated planets, each) and invaded the rest. In that specific setting, I saw it as a viable strategy, but not otherwise. I do have to say that I probably won't build them again any time soon unless I encounter a similar challenge.

With all of that having been said, I do have to say that, if you haven't destroyed a star system with a Terror Star, try it. Just once. It is awesome!