Hi,
Yes, it is possible. The way I would do this is having two runbooks. Parent runbook gathers the VMs that needs to be stopped/started. The child runbook stops/starts a single VM. using Start-AzAutomationRunbook you will start the child runbook from the parent. The start will be regular for each so each runbook has a single VM information for input. This is somehow parallel as the runbook is just started but you do not wait for the job the finish. I would use this approach as allows better visibility in case a VM is not started for some reason and you need to troubleshoot any issues with the execution of your code. Another option is the one you have mentioned with -NoWait switch for the Start/Stop cmdlets for VMs. That is possible and the benefits of it are faster execution as you do not have to start more runbook jobs you can do it in single one. With faster execution also the costs will be lower due to less runtime. Of course you will loose any visibility if the action was fully successful in case of issues occurring.
Update: I have missed the part that you also want to change the SKU. In such case you will have problems with -NoWait as you will be able to use only for the start job but not for the Stop job as you will have to wait the stop to finish to change the SKU. So in such case -NoWait will not be suitable as you still execute in sequential order and only for the starting you will not wait for the final result. When changing the SKU it is also good to see if the VM will be started as the VM might not be able to start due to capacity issues or quota limits.
Please "Accept the answer" if the information helped you. This will help us and others in the community as well.