On CR, it probably is reasonably compared to a bodak or mohrg (though it has way more SAs). So CR 8 is probably reasonable.
Yes, I'm happy with CR 8.
Being able to cast spells as an 8th-level cleric and fold a pair of origami creations AT THE SAME TIME is quite effective, I might even see it being CR 9.
For rejuvenation, he crumples into a ball of paper (maybe then decaying to dust?). Then a sword charm appears like for all the others.
It doesn't actually say the Paper Warrior literally turns into a ball of paper, the description is "there is the sound of crumpling paper as he collapses into a ball".
As for the sword charm, we have "Within a drawer in his desk there is a prayer cloth with two cure disease and three cure serious wound spells. There is also a box of eight pen nibs, but one is really a katana charm that fits into the medallion."
So how about:
Rejuvenation (Ex): The Paper Warrior cannot be destroyed through simple combat. If "destroyed" its body and equipment collapses into a ball with a loud rustling like paper being crushed, following which its remains crumble into ash at the slightest touch. A pen nib shaped into a small sword-shaped charm pendant simultaneously appears concealed somewhere nearby (typically in a writing case mixed with normal pen ribs). Finding this concealed item requires a DC 15 Search check or DC 25 Spot check.
The following night, the Paper Warrior reappears at full strength at whatever place it haunted and the sword charm vanishes. The Paper Warrior can only be destroyed permanently if its sword charm is destroyed before it rejuvenates. A typical sword charm is a Fine sized object with 20 hp, hardness 12, and break DC 24.
Whew, this is taking a long time.
Yup! At least we only have two left.
Upon reflection, I'm wondering whether we should add "Some sword charms require a special procedure to destroy." to end of all the Rejuvenation entries.