How to preserve coated popcorn?
The popcorn's problem is effectively staling -- and a sufficient coating will help to prevent this problem.  You may need to add the caramel at a low enough viscosity to get a good coating on the kernels.  You can always give them a second coating, if necessary.

It's also worth nothing that many of the places that sell packaged pre-popped popcorn tend to use 'mushroom' style popcorn.  I assume it's so that there's less breakage of the popcorn during transport, but it's also possible that there are other reasons (eg, slower staling due to reduced surface to air ratio).