You don't choose the new target for the spell or ability until Bolt Bend resolves. You must change the target if possible. However, you can't change the target to an illegal target. If there are no legal targets to choose from, the target isn't changed. It doesn't matter if the original target has somehow become illegal itself.

If a spell or ability targets the same player or object multiple times, you can't target it with Bolt Bend.

Once you've cast Bolt Bend, losing control of all creatures with power 4 or greater won't affect the spell or cause you to pay more mana.

To determine the total cost of a spell, start with the mana cost or alternative cost you're paying, add any cost increases, then apply any cost reductions. The mana value of the spell remains unchanged, no matter what the total cost to cast it was.

Once you announce that you're casting Bolt Bend, no player may take actions until the spell has been paid for. Notably, opponents can't try to change whether you control a creature with power 4 or greater.

The single target that the target spell or ability targets doesn't have to be a creature you control with power 4 or greater.

If a spell or ability targets multiple things, you can't target it with Bolt Bend, even if all but one of those targets have become illegal.