There are a couple things at play here, some involving the paper, some involving your skin. For one thing, what part of your body comes in contact with paper the most? Right, the majority of paper cuts happen on the fingers and hands. Your hands are pretty complex sensory instruments, and they're absolutely jam-packed with nerve fibers called nociceptors.
These guys sense temperature, pressure and pain, and there are more of them per square inch in your hands and fingers than most other parts of your body. Injuries there are noticed much more than similar injuries elsewhere. The same small paper cut on a less nerve-dense area, such as, say, your leg, won't send nearly as many pain signals to your brain.