It can definitely go in the compost bin. In fact they don't like shredded paper for recycling as the fibres have been chopped so short it can only be recycled into low grade paper.

When you put it in the compost, mix it up a bit with the other stuff so you don't just get a big wodge of shredded paper in a lump