How does a bank create new money when it pays its own staff?
If an employee performed work there is a liability called "current liabilities". Paying into the employee's account is just changing one kind of liability into another kind of  liability of the same size so total liabilities is unchanged and total assets is unchanged. The new liability is a recorded as a deposit. 

Paying the employee with an amount of cash reduces assets and reduces liabilities. 

@IñakiViggers is correct, of course, that part of the assets were the result of interest earned and fees charged. My answer addresses only what happens at the instant in time the employee is paid.