Would this be a suitable ds to distribute node state for caching indices? Let's say two nodes have a set of N (possibly overlapping) keys and I want both to know all keys of each other for request routing (request for n \in N preferably to node with n in local cache).

Yes. I think G-Sets (3.3.1) are what you are looking for.

https://dsf.berkeley.edu/cs286/papers/crdt-tr2011.pdf

CAP applies here.

If you ask your cache for a value, it could choose to reply now, with the information that it has - favouring A.

Or it could wait and hope for more accurate information to return to you later, favouring C.

'Cache' seems to imply that it's built for availability purposes.