It’s a problem as old as WP, or even older…
You can’t set cookies, or send any other headers, if any of the content of the site is already sent.
You try to set cookies using init hook. And it is OK in most cases, since no output should be printed yet. But… Not all code is written correctly.
There are many other thing done before init. Take a look at actions run during a typical request.
As you can see… Themes get loaded before init hook. And so do plugins.
So if their code cause any warning/notice (and the debug is on) or they generate any other output, then you’ll get error while setting cookie.
Another popular cause for this problem is using closing PHP tags (?>) at the end of files. If there is any white characters after that closing tag, then it’s treated as output also.