Most CDN's do request coalescing and so you need to tell the cache to never store any cached response that contain cookies, they should be stripped out before they are stored. Current we (catalyst au) do this with varnish config but I think it's possible to move this into extra Cache-control headers that in theory should be honored by any cache or cdn layer.
If you want to receive cookies at your origin but you don't want CloudFront to cache the Set-Cookie headers in your origin's responses, configure your origin to add a Cache-Control header with a no-cache directive that specifies Set-Cookie as a field name. For example: Cache-Control: no-cache="Set-Cookie". For more information, see Response Cache-Control Directives in the Hypertext Transfer Protocol (HTTP/1.1): Caching standard.
Docs for Cache-Control specifically around stripping headers:
So I not 100% but I think we can do something like:
1) whenever we set a new cookie, ensure that we also send a header saying that should be stripped out
2) I'm fairly sure it is valid that we can send multiple Cache-Control headers which means we can split this logic out and send this header just in the very small number of places where we set a cookie, and not in the large number of other places which set other Cache-Control headers which would be near impossible to fully track down in core and all plugins.