You have to a large degree answered the question yourself, really: clann is indeed a very early loan word.
Like Common Celtic, Common Insular Celtic had no /p/, but it had /kʷ/.
The Brythonic branch changed /kʷ/ to /p/ (keeping the labiality, losing the velarity) quite early on, whereas in the Goidelic branch, /kʷ/ merged with /k/ (retaining the velarity, losing the labiality) somewhat later on.
In the earliest Ogham inscriptions, there are still separate letters for /k/ and /kʷ/, so we know that the change took place fairly close to the ‘proper’ attested stage of Early Irish. Sadly, we don't have any direct evidence that dates the Brythonic change, at least not that I know of. But unless I'm misremembering (and I don't have access to my works on Brythonic sound change at the moment), it can be positively shown to have predated certain other changes that definitely happened quite early on.
At the time when clann was borrowed, Brythonic /kʷ/ => /p/ had already taken place, but Goidelic /kʷ/ => /k/ had not. In other words, Brythonic *pland was borrowed with the closest equivalent available (the only unvoiced labial plosive in the language), as *kʷland, which later lost its labiality and became kland (orthographically since Old Irish cland, later on clann).
Once /kʷ/ was lost in Irish, however, there was no good, existing unvoiced plosive to use as a substitute for /p/, and it was around that time that they started using this hitherto foreign phoneme in loan words, reintroducing the long-lost /p/ back into the Irish language. This was still fairly early on, of course, predating the earliest ‘proper’ Old Irish sources (the Milano and Würzburg Glosses)—early enough, also, that this new /p/ became a natural part of the system of initial mutations on a par with /k/ and /t/, all three being subject to both lenition and nasalisation.
I am certain there are other words (either directly from Latin or through the medium of Brythonic) that show a similar route, but I cannot think of any off the top of my head at the moment.
Edit: Not true, there is one other well-known example I can think of: the Irish word for Easter, Cáisc, is derived via Latin pascha and Greek πάσχα ultimately from Hebrew (see etymonline for details). That shows the same development.
As Colin Fine mentions in the comments, another parallel example is corcair ‘purple dye, lichen’ and its derivative corcra ‘purple’. This word is perhaps not borrowed directly from Latin purpura (itself borrowed from Greek πορφύρα ‘purple (colour, dye, clothes, etc.)’), but it definitely has the same source and shows the same development of *p being borrowed as *kʷ > k.