Many of your ideas are based on faulty assumptions.
S meaning small enough to fit into iteration which also does not apply to Kanban
The rule of thumb is generally that a story should move through the system in 2-3 days.
You link to the Agile Alliance page that defines INVEST. However, that page links to the XP123 blog post by Bill Wake that captures the original definition of the INVEST mnemonic. If you look at the original definition of "Small", it doesn't mention iterations at all. It does say that Stories "typically represent at most a few person weeks worth of work", but some teams may choose to make them smaller.
The S from INVEST should still be applied to whatever your work item when applying kanban, but how big S really is depends. You are right that you can't use your iteration length as a boundary for the size of the work item if you are following a leaner approach, but you would be able to if you are applying kanban to Scrum.
the E meaning easier estimation which does not apply to Kanban
This is a relatively common misconception. There are two techniques around estimation in kanban approaches.
The leanest approach to estimation is to decompose the work into roughly equal sized chunks, where each work item that moves across your kanban board is roughly the same size and you can simply count number of work items and time to progress. However, you can also use relative measures (such as story points) or time measures (person-hours) as well, but you would need to consider these when computing many of the metrics commonly used in a kanban system, which adds complexity and introduces additional room for error. My recommendation is to work toward the first approach, but if you are transitioning from something like Scrum, it may take some time to get there.
Both approaches are still estimation, though. If you aren't thinking about the size of the work, you aren't able to determine if two pieces of work are roughly the same size.
The point of David Anderson's comment is to consider why you are estimating and your current approach. How much time are you investing in estimating using your current technique? How much value do you get from it? Why are you doing it? I think it's much like the #NoEstimates movement - it's not opposed to all estimates in all cases, but rather a drive to think about what you are doing and why you are doing it.
But, to the heart of the matter:
If user stories need to be small for Kanban, why do they need to be small?
Is the reason due to WIP limits? This is even more confusing since WIP limits are empirical.
There are two reasons for small work items when applying kanban: feedback and predictability.
Smaller work gets done faster. It goes all the way through the value stream and delivered to the next stage in the process. You can get feedback on the work, which would allow you to change your backlog based on the changing situation. You can also get feedback on the process, finding bottlenecks or opportunities for improvement based on how long the work was in each activity.
If the work is equally sized or you can easily tell the relative size, as work moves through the value stream, you can predict how long it will take to go from an arbitrary point in the backlog to done, assuming it's not reordered. Or you can tell how long a work item typically lives in a particular stage of development. Equally sized work makes this much easier, but after some work items have passed through the process, you can use historical data to make predictions about new data. And if you're following an empirical process and inspecting your processes and methods regularly, you are hoping to improve, which could be time reduction.
Actionable Agile Metrics for Predictability: An Introduction by Daniel S. Vacanti is a good intro to metrics around kanban and other lean approaches. I found it a little dense, but very informative.