This trick was almost certainly modeled on ancient magic squares, such as “Sator, Arepo, Tenet, Opera, Rotas,” a famous talisman used in the Middle Ages, which is also an anagram for Pater Noster, the opening words of the Lord's Prayer, arranged in the form of a cross, with A and O (alpha and omega, from Revelation 1:8) sandwiching the Ts to read ATO. See Richard Kieckhefer's Magic in the Middle Ages, 1989, p. 77, who cites the earliest known instance of this magic square found in a first-century Christian home in Pompeii. While the Mutus, Dedit, Nomen, Cocis matrix is a five-by-four grid, rather than a square, its resemblance to ancient Latin magic squares is too striking to be easily ignored, as well as its “magical” purpose. If this is granted, the trick may be one of the earliest card tricks invented.
In Claude Gaspar Bachet's Problemes plaisans et delectibles, qui se font par les nombres, 1624, p. 143 of the second edition, a basic system is given for constructing layouts ranging from twelve to forty-two cards. And instead of relying on four mnemonic words to identify the thought-of pairs, a system of positional relationships is employed. Bachet also gives the method for dealing the cards into the required pattern. This reference comes from Bill Kalush.
The earliest published record of the use of the mnemonic words Mutus, Dedit, Nomen and Cocis appears to be Edme-Gilles Guyot's Nouvelles récréations, physiques et mathématiques, 1740, p. 28 of the Hugard translation (unpublished). It was later described in William Hooper's Rational Recreations Vol. 1, 1774, p. 70 of the second edition, where it appears as “The Ten Duplicates,” the title for which it would be known for a great number of its earliest appearances in print. Later it was frequently called “The Pairs Re-paired.”