On June 26, 2014 AWS released proper Vary: Origin behavior on CloudFront so now you just
Set a CORS Configuration for your S3 bucket:
<AllowedOrigin>*</AllowedOrigin>
In CloudFront -> Distribution -> Behaviors for this origin, use the Forward Headers: Whitelist option and whitelist the 'Origin' header.
Wait for ~20 minutes while CloudFront propagates the new rule
Now your CloudFront distribution should cache different responses (with proper CORS headers) for different client Origin headers.