Thanks for the replies!
Merging the documents and sending a single big document to GCP is not feasible due to the clients workflow and the general system architecture.
The time is almost constant - takes about 10 seconds per document (all documents are single page pdf documents), so we get a big queue of print jobs in cloud print and they are getting printed one after the other - but quite slowly. Of course it would speed up printing if all jobs for a single printer would go into a single large pdf, but this has to be done at GCP's end - and we are using printer configurations/different trays etc. so this is not as easy as one would guess.
Unfortunately we used Java Print API before switching to GCP, so they of course compare it to the blazing fast printing they used to get before.
I'm at the customers site on Thursday so I try to get some more numbers and printer details. They have a bunch of different legacy printers, no native cloud printers.