Yep, commenter is right, do it in the background. But then you have to wait for the background stuff implicitly:
while ! nc -vz localhost 4000; do sleep 1; done & pid1=$!
while ! nc -vz localhost 4001; do sleep 1; done & pid2=$!
while ! nc -vz localhost 4002; do sleep 1; done & pid3=$!
while ! nc -vz localhost 4003; do sleep 1; done & pid4=$!
while ! nc -vz localhost 4004; do sleep 1; done & pid5=$!
wait $pid1
wait $pid2
wait $pid3
wait $pid4
wait $pid5
This way, all five processes are started in parallel in the background, then almost at once the first wait
is started. This one waits until the first background process is finished, then the second wait
is started; probably this won't have to wait for long because the second background process will probably finish around the same time as the first.
So, in theory, this will take about as long as the longest of the five processes.