The 4K limit you read about is for the entire cookie, including name, value, expiry date etc. If you want to support most browsers, I suggest keeping the name under 4000 bytes, and the overall cookie size under 4093 bytes.
One thing to be careful of: if the name is too big you cannot delete the cookie (at least in JavaScript). A cookie is deleted by updating it and setting it to expire. If the name is too big, say 4090 bytes, I found that I could not set an expiry date. I only looked into this out of interest, not that I plan to have a name that big.
To read more about it, here are the "Browser Cookie Limits" for common browsers.
While on the subject, if you want to support most browsers, then do not exceed 50 cookies per domain, and 4093 bytes per domain. That is, the size of all cookies should not exceed 4093 bytes.
This means you can have 1 cookie of 4093 bytes, or 2 cookies of 2045 bytes, etc.
I used to say 4095 bytes due to IE7, however now Mobile Safari comes in with 4096 bytes with a 3 byte overhead per cookie, so 4093 bytes max.