I have a script on several actors at the same time (via a cloak spell) and I only want one of them to "complete" the script once it starts.

The script that would run completely toggles a global so the other scripts would see this global set and not run.

But it seems that will not work all the time because of multithreading.

How do I sidestep the multi threading in this situation?

http://www.creationkit.com/Threading_Notes_(Papyrus)#Locks. While Papyrus is multi-threaded, one thread will get to the lock first and claim it, then all other threads of the same script must wait. The claiming thread can set the 'Me First' flag and release the lock, on which the other threads will one by one claim the lock, see another thread got there first and abort.