First off where are her toys when he gets into them? Are they laying around the house, or in her bedroom??

A dog's mentality is this: if its on the floor, its mine. So if you don't want him to get into something, make sure its not laying on the floor!

It they are in her bedroom and he gets them off of her bed or something, then either gate her bedroom, or keep her bedroom door closed.

You are doing the right thing by replacing the stuffed animals with something of his! You are telling him, "this is not ok to chew on, but this is". He WILL get it eventually, and once he learns the meaning of "no" (or the meaning of YOUR no) then he will get it.

Swatting with a newspaper I never recommend.. physical pain never teaches a dog anything except fear. A time-out though is more than acceptable. Some use a bathroom for time-out, so whatever works for you!