Paper airplanes' wings are completely flat, unlike the droplet shaped curvature of a full sized wing. How does a flat wing generate any lift if both sides have the same air pressure?
Paper airplanes create lift just like any other airplane. Don't let the wing cross section confuse you; what the air "sees" is a different shape.
When a flat plate flows through air at a positive angle of attack, the stagnation point of the flow (where air splits into an upper and a lower flow path) sits slightly below the forward edge of the wing. Now the streamline just above the one which hits the stagnation point has to negotiate the sharp corner of the leading edge, which will cause it to separate from the surface. This creates a small separation bubble which to the streamlines further up looks like a round leading edge, and since the rest of the wing has no curvature, the flow will attach again soon. The bigger the angle of attack gets, the farther back the stagnation point will be and the bigger the separation bubble becomes. At some point, which is promoted by leading edge sweep, the separated flow will not reattach, but produce a vortex, like the vortex which provides lift on delta wings.
The picture above is from a simulation; see the full video here. Note the red color on the forward part of the upper side: This indicates low local pressure, which is needed to make the outer air negotiate the leading edge plus the separation bubble (see here for an explanation on the molecular level). In the separation bubble, low pressure is not accompanied by high flow speed since the separation turbulence has eaten up most of the kinetic energy.
The actual nose radius of the paper wing does not matter, and it might even be zero (like when you fit razor blades to the leading edge): The air will create its own airfoil shape by padding with separated air what cannot be reached with attached flow.
Paper airplanes have a low enough wing loading that their angle of attack is low and the separation does not become too big. All it needs is a center of gravity at the quarter chord of the wing; that is why you need to fold the piece of paper first.
It is interesting to watch a slightly tail-heavy, delta-shaped paper airplane fly: It will gradually reduce speed and will start to rock its wings when it approaches stall. Once one wing is going down, the sudden increase in its local AoA will increase lift so much that the rolling motion reverses, without noticeable yawing. The delta-shaped flat plate has effective roll damping right into the stall. The lack of yaw is mostly due to the high yaw inertia, but indicates also that drag buildup is moderate at best.
Of course, after a few periods of rocking the nose will drop and it will pick up speed like any well-behaved airplane.
How does a flat wing generate any lift if both sides have the same air pressure?
The two sides do not have the same pressure.
A flat plane can still produce lift (think of putting a plate out of the window of a moving car, if you point it slightly upwards it will strongly push upwards, that's lift). The main reason is the Kutta condition that must be satisfied at the trailing edge: this will create circulation around the flat plate, generate a pressure difference and thus generate lift.
Paper airplanes will inevitably come down not because they do not produce lift, but because they also have drag (and no thrust), that will slow them down and hence reduce the lift generated.
Because it takes the path of least resistance. There is lot less drag in slipping forward through the airmass as it falls than in falling flat towards the earth.
Think about it: If you stuck a putty knife in a block of jello at a 45 degree angle, then pulled it straight towards you, would it come straight towards you, or might the blade tend to angle towards one side or the other? (depending on which direction the closer edge was...)
Would you say that this phenomenon is due to a differential in gelatinous pressure, or that the putty knife produced lift? I wouldn't. I'm not an engineer, but I would say that the knife simply took the path of least resistance.
It is true that a flat wing can produce lift, but a paper airplane's wings are not flat on top. They have a folded piece on top that bows slightly up. Air has to flow a longer distance over that slight curve as compared to the bottom of the wing, just like an airplane. The faster air causes a pressure drop relative to the bottom of the wing, thus lift.