It was a multifaceted problem, and was ultimately a design flaw/oversight rather than someone saying "I think 4kB is enough memory to store all the textures". The problem is less that the cache was small, it's more that Nintendo's plans for how awesome RDRAM and a unified memory architecture didn't pan out.
Problem #1: There was no dedicated video memory. All RAM on the N64 was shared RAM. So framerates tanked if you didn't have most of your stuff in cache. Keep in mind the framebuffer also lived in this unified memory area, so the video chip was already very noisy on the memory bus.
Problem #2: The unified shared system RAM was RDRAM, not SDRAM. And the latency on RDRAM is absolutely terrible. So the already expensive cost of using RAM was compounded.
If the N64 did what the playstation and saturn did and just have dedicated video/system RAM, and made this RAM relatively low latency SDRAM instead of the relatively high latency RDRAM, this 4kB limitation wouldn't have mattered.