The icy-pole melts because it absorbs heat. Heat can be absorbed in three main ways:
Radiation: The light and heat and other kinds of electromagnetic energy waves given off by everything in the environment hit the icy-pole, warming it up. (Put the icy-pole in direct sunlight, and it will melt faster.)
Conduction: If the icy-pole is in physical contact with something warm, heat is transferred directly from that object to the icy-pole. (If you put warm your finger on the icy-pole, heat transfer will melt that part of the icy-pole and make your finger cold.) Note that the icy-pole is in physical contact with the atmosphere even if it is touching nothing else.
Convection: Heat can be transferred through a fluid (i.e. liquid or gas) by moving currents. Heat can be transferred to your icy-pole from the pocket of air around it, cooling the air and slightly warming the icy-pole. Convection (wind) can then move the cooler air away and replace it with warmer air, which can melt the icy-pole further.
Overall, the speed your icy-pole melts at depends on a combination of these things.
If the icy-pole is exposed directly to the air, then it is exposed directly to light and heat radiation. It does not gain much heat from conduction, as air is a good insulator (doesn't transfer much heat). Convection will slightly increase the heat it gains from the air.
If the icy pole is wrapped up tight in newspaper, it is no longer exposed directly to light and heat, so the effects of radiative heat transfer will be lower. Convection will also be reduced since any air trapped inside the newspaper will not be able to move as much. But the newspaper will be directly in contact with the icy-pole, and newspaper is not as good an insulator as air, therefore heat transfer via conduction will increase.
If the icy pole is inside a box made of newspaper that does not touch the icy-pole itself, then as in the previous case, heat transfer via radiation and convection will be lowered. Heat transfer via conduction will remain the same because the icy-pole is still only in physical contact only with the air.