The paper method only ensures that you get the nozzle-to-bed distance reasonably consistent in all the places your printer checks it, to ensure that the bed is trammed, i.e. straight relative to the X and Y axes of the printer, or "level." It doesn't guarantee that your Z offset is actually correct to produce a good first layer, and depending on how your particular printer runs its bed leveling/Z offset program it may in fact guarantee that it is incorrect every time.
If you're going to use some manner of gauge material (paper, one of those plastic cards, a feeler gauge), step 1 is to determine what, exactly, your printer does to set its Z offset and whether or not that's taken into account when you're sliding your piece of paper or whatever under the nozzle. Some printer firmwares further compound things by calling their Z offset adjustment program "bed leveling" when that's not what it is. (My old Qidi was guilty of this. "Fast leveling" was actually just Z offset adjustment in the center of the build plate, and "Full leveling" was actually a four-points bed level check operation.)
