Is it possible to put the food bag behind a closed closet? Or another room?

With the deck, maybe you could spray some of that bitter apple stuff on it? Or watch him carefully and tell him to stop if you see him doing it?

Maybe you could put some fencing around your trees

With digging, you could lay down some chicken wire to cover your yard, it will hurt his paws if he digs, and the grass will also grow better.

Good luck!