A British English expression that comes from, of all places, the accounting world! In the early 20th century, as rubber stamps became a common office accessory, accountants would stamp (or put) a red PAID onto invoices that had been dealt with, right next to the total amount that had been paid. Hence "put paid next to".
This timing corresponds to the earliest use of this phrase in the written record, where it has variously meant to finalise or to finish off or to completely destroy. Some usage examples:
I haven't made these examples up - as you can see they are all taken from recent British
press. This phrase is also in common use in other
Commonwealth countries, like
Australia and
New Zealand.