It’s hard to tell because the deviating form in Latin is actually the nominative singular, which is why vocab lists include the genitive singular as well. All other forms have the same stem aside from Nom. Sg. A few examples are:
senex - senēs (elder)
rēx - rēgēs (king)
index - indīcēs (index)
So really anything could work as long as it ends on -ēs in plural and starts with kleen-.
Haha! It would be unconventional to use a double s in any form aside from the s-perfect, which is the time form of a verb, the superlative forms of adjective, or beyond the first two syllables. After a bit of research an accurate word would be either a g, k, or a c (all formed in approx. the same area of the mouth as x) instead of the x followed by the -ēs. Trying to pronounce Kleenex with an i before the g, k or c sounds less like Kleenex than index sounds similar to indices. The transition from a vibrating sound like the n to an i also feels unnatural at that part of a word, normally it comes after a t or a d sound. Also the name itself stems from the verb “to clean” and the latin suffix -ex. If it suggests something like a “cleaning king” the resulting word could therefore be Kleenegēs, but Kleenecēs is not off the table.
However, my initial suggestion is inaccurate. The senex-style plural (Kleenēs) is a special case of which it ism’t resolved why senex drops its -x entirely on flexation.