Hmm, that does sound a bit challenging I must admit. TK has another component in there, KGrid, I wonder if that would help you ? I have not used it at all, I use KMemo.
I have not tried to paste anything other than (marked up) text and images into KMemo. It does apparently have a table mode, from the wiki -
"advanced table support with full row/cell formatting and even with cell merging support, so even very complex tables created with MS Word can be loaded, saved, viewed and edited in KMemo"
So, I guess that must mean it can be done, the problem must relate to the format you are pasting. When we copy and paste, the source application lists the formats it can deliver in, the receiving application looks through that list and chooses something it likes. Usually plain text is the fall back when all else fails. So, do you see some plain text content arrive in the KMemo ?
EDIT: I just tried to paste an Open Office table into a tomboy-ng note (which is basically a KMemo) and the table content copied across cleanly but no sign of a table structure. That says to me it is, in fact, deciding to deal with just the plain text parts of the paste.
Davo