I think people say to avoid colors on packages and newspapers because it used to be common that these would include small amounts of metal. After briefly looking it seems almost everyone is using inks that are cheaper and contain no metals. Most glossy stuff is just a wax based coating so shouldcompost. To make it compost quicker you can soak it in water or leave it out in the rain. That being said I avoid adding those things into my bedding for the worm bin, in case they are more sensitive or something.
Yeah it'll compost easily. The printing or coating counts for so very little of the mass of the finished compost (unless you're using it exclusively as your source of carbon) that it really won't matter that it had a little ink or wax on it.
Even still, most of the biological and chemical processes that occur during composting render most toxins inert by locking them up in longer carbon compounds.
Frozen food boxes and beer and coke boxes are made of paperboard with a polyethylene additive (wet-strength). The wet-strength is usually mixed in with the paper fibers during manufacture and while it presents a problem for pulping and recycling the boxes, i'm not sure how it would fare in the compost. The plastic will not end up in a thin sheet as you would get with milk/juice boxes. I'm not sure how you feel about countless tiny pieces of plastic in your garden (maybe too small to see?), but i'm not that excited about it.
If you decide to not use them in your compost pile, you can turn them into biochar, all you need is a can with a lid and a heat source that can be limited to around 250 degrees. The can lid should be able to seal fairly well so not a lot of oxygen can get in. The lower heat means that most all of the "plastic" will gas off while the paper chars. It won't take very long either, probably under an hour. Once you have charred the paper, it could be placed in the compost pile for further processing then finally make its way into your soil.