Your example is not an ideal one to illustrate the underlying principles, as the factors that prevent you from unfolding the paper involve many trillions of molecular interactions within the paper, which amount to a very complicated mechanism to visualise. Consider instead a simpler set-up with vastly fewer moving parts as follows...
Imagine it is the start of a snooker game. The red balls are arranged in a triangular layout. You are able to scatter the balls with a well-directed shot of the white. The interactions between the individual balls are governed by simple equations that are all clearly time reversible. Consider, however, the difficulty of reversing the effect of the dispersal- how could you, with a single shot, cause all the reds to re-assemble in triangular formation?
By contrast, consider Newton's cradle- the arrangement of identical spheres each suspended to swing in a fixed plane. The interactions of the balls are trivially reversible.
The key difference between the two examples, each of which involves collisions between spheres, is that in the case of the snooker shot a single action can lead to a fantastically large range of possible outcomes- the balls could spread anywhere. When you try to reverse the process, you are imposing a much tighter constraint- there is only one specific outcome that would satisfy you, namely that the balls were rearranged in a triangle.
The principle is analogous to a card trick. The magician asks you to take any card- it does not matter which, so the action is an easy one for you to get right. For the second half of the trick, however, the magician must find the specific one you picked, so the odds of doing so at random are greatly reduced.
You will find that almost all irreversible processes are so because they create a large number of random changes, such that the chances of every one of them being exactly reversed is effectively zero.
In the case of folding paper, the action disturbs the arrangement of countless fibres that had been compressed to lie in a certain plane when the paper was manufactured. Depending upon the materials from which the paper was made, and how sharply the crease was formed, you might be able to eliminate signs of the crease by pressing it with a hot iron, which recreates the heating and compression that were applied in the manufacturing process.
I am not convinced that it is useful to consider entropy to aid one's understanding of why it is difficult to unfold paper perfectly. Consider your example of gas in a box. If you have gas compressed by a piston and the piston is with withdrawn some distance, the gas expands naturally and there is an increase in entropy. The expansion and increase in the entropy of the gas is easy to reverse simply by pushing the piston back to its original position. The difference between that, which is easy, and the perfect unfolding of the paper, which is difficult, is not principally a question of entropy.
Indeed, take a gas in equilibrium in a sealed insulated box. Imagine the position of the molecules at any one instant, then consider the challenge of precisely recreating that arrangement at a later time. The gas is at equilibrium in a sealed insulated box, so there has been no change in entropy, yet the probability of recreating the original arrangement is vanishingly close to zero.