The tricky part is how to pass the parameters to the Start-AzureVM cmdlet.
This code assumes the name of the vm is equal to the name of the ServiceName (the name of the Cloud Service)
$vms = Get-AzureVM
$vms | % {Start-Job {Start-AzureVM -Name $args[0] -ServiceName $args[0]} -ArgumentList $_.Name}