Inside a library of common functions (Instruction Set ----> High Level Program) is there information of how many clock cycles they use?
Even with a RISC processor like this, where all instructions take the same number of cycles, it is going to be difficult if not impossible to determine the exact number of cycles (and thus time) of a given library routine. Especially considering the that every conditional decision within each library call may introduce more or less instructions (and time) into the execution path. If you were working with a full debugger and simulations system (which Atmel may offer at a price), it would then be possible to set breakpoints and measure precise timing of every possible case of every routine. But I suspect it would be frustrating unless the library functions were designed to ensure all cases resulted in the same timing.

That being the case, if I were you and had these concerns I would employ an oscilloscope with at least dual trace and trigger capability to test timing and synchronization, in a more deterministic fashion. That is, I can start any number of test sequences and toggle various digital pins to change output state when a given task completes. This would allow me to clearly see both the total time to complete various tasks, as well as differences between various cases. The result you are hoping for, which I think you'll get given the speed of the CPUs, is that you will have more than sufficient extra time, and all your tasks are be completed in time that is insignificant compared to the much slower speed of the actual 9 bit serial words.

Of course if it turns out that even with negligible processing time, you are still not satisfied with being limited by the speed of the serial transmission, then you'll have to either use a much faster bit/baud rate, or you will have to use multiple processors (each with their own serial I/O). then they can all prepare their data and be triggered to send simultaneously, from a single command (such as a single digital I/O point signalling all CPUs to send). 

Good luck! Hopefully you'll find the Arduino speed is not an issue, and sending data to all your servos one at a time is still adequate. 

And I don't know if it matters, but all arduino processors I know of have several direct PWM outputs. 

But also be aware there are probably better forums than the electrical engineering forum for specific coding or processor capability questions.