> This means that more and more healthcare workers spend their time doing paperwork or customer service work that could be done by anyone

The obvious solution seems to be reducing the required paperwork rather than hiring more staff to handle the paperwork, and this seems to agree with your experience when you described "unintegrated time recording systems".

That said, I wouldn't be surprised if too much bureaucracy was also partly to blame, because that's what happened here in Canada.