As I understand it a check is a specific kind of shtar mentioned in the gemara. IIRC there is a case in the first perek of Bava Metzia where someone writes to the chenv’ni to pay xyz to his creditor. That case is the etzem metzius of a check — pay ot the order of ploni.
Paychecks might complicate things because direct deposit creates issues of shibuda d’rav nasan, but at the end of the day, the employee is the “levi” figure in the shibud.