For example, if you were to roll a piece of paper into the shape of a hollow cylinder and then try to return the paper to its original, flat shape, it would naturally roll to the cylinder when you let go. Why would an originally flat surface, when changed to posses two curves roll?
First, I would note that not all flat surfaces are represented by a sheet of paper. Flat rubber sheets for example, if rolled, will usually unroll themselves flat again.
The answer will lie in an understanding of the forces at the molecular level. Rubber is made of coiled polymer chains. You can distort those chains by pulling, pushing, rolling, and etc, but when the distortion force is removed, the polymer chains will likely return to their coiled shape, and the rubber to the shape you started with - as long as you remained within what is termed the linear viscoelastic region of the material, where stress and strain are linearly related. If you move out of the linear viscoelastic region, you typically induce plastic deformation in a solid (stress > "yield stress"). Rubber's ability to be flexible is one property that makes it useful. Most material's will have a combination of elastic and viscous responses to applied stress' or strains.
[As mentioned in a comment below, rubber can endure large deformations and still return to its original shape. However there is also the phenomenon of "compression set", that occurs with rubbers/elastomers below their yield point. As with most viscoelastic behavior, time under stress can play a role in both responses.]
To move onto paper, first we need to understand what it is. Wikipedia tells us:
Paper is a thin sheet material produced by mechanically and/or chemically processing cellulose fibres derived from wood, rags, grasses or other vegetable sources in water, draining the water through fine mesh leaving the fibre evenly distributed on the surface, followed by pressing and drying.
Thus paper is a collection of fibers held together by molecular forces. It is interesting that we still don't have a complete picture of the forces holding these fibers together as this recent (2013) paper indicates:
Several mechanisms have been suggested to play a significant role in forming the fibre-fibre bonds that lead to the fibre network that we call paper. In the past, the following possible bonding mechanisms were considered: hydrogen bonds, mechanical interlocking, electrostatic interactions, interdiffusion of cellulose molecules and van der Waals forces. More recently, microcompressions, capillary bridges and stress due to the drying process have been under discussion. What is agreed is that all of these mechanisms contribute in some way to bonding two pulp fibres together. It is still not clear, however, which of these mechanisms dominates or if an interplay of several mechanisms is relevant.
When studying the viscoelastic response of materials, there is a test termed a creep/recovery test. In this test a constant force (or stress) is applied and the strain (or response) of the material is monitored. Usually there is a large initial strain followed by 'creeping' of the material. This is like sitting down on a sofa. There is first a large deformation of the cushion and then you will slowly depress it (sink further into the couch) even further over time. Again, if you remain in the linear viscoelastic region of the material, when the stress is removed (you get up from the sofa), the material will 'recover' its form. If you did not stay in the linear viscoelastic region, there will be a permanent deformation in the material.
This is what a creep/recovery test (with permanent strain induced) looks like:
Reference: R. D. Gustafson, A. L. McGaughey, W. Ding, S. C. McVety and A. E. Childress, "Morphological changes and creep recovery behavior of expanded polytetrafluoroethylene (ePTFE) membranes used for membrane distillation", J. Membr. Sci 584 (2019) 236–245.
So with paper, I would say it is easy to enter the plastic deformation region by rolling it, though I think it also depends upon how tightly you roll it. You are essentially performing a creep/recovery test. If you roll it tightly and hold for a long period of time, you will get less recovery, than if you slightly rolled it and let go immediately. And the structure of paper on the microscopic level means it is easy to distort in this manner. (Much harder to do a creep/recovery test with your hands and enter the plastic distortion region by pulling along the planar direction of the paper!)
Hope this helps.