First, if you have used newspaper in the litter box, we don't want to use it on the bed. It will send mixed messages to your lad. He will see the bed as being covered in an acceptable litter substitute. Therefore, you need to either close the door and deprive him access while he isn't supervised or use plastic to cover the bed.
Otherwise, if we have an elderly cat that can use the box for urine but not feces and has had no changes in environment or fecal consistency, then we'd be less worried about bladder based issues, stress induced inappropriate marking (where territorial marking can manifest this way, but is less likely since there have been no changes in his world), or underlying systemic/metabolic causes for his signs. Instead, we really need to rule out/address arthritis as a underlying trigger for this new inappropriate behavior. (It may even be that he has a twinge/inflammation that is making him feel more sore then usual).
It is not uncommon to see old age and associated arthritis manifest in this manner. . Cats, unlike dogs, go to great lengths to modify their lives around avoiding things that cause them discomfort. Where a dog will run on a sore leg until he can’t use it, a cat will just decrease doing the things that are causing the pain. It is wise for the cat, harder for us to pick up when there is a problem.
Unfortunately, in cats with pain derived litter box issues, trips to the litter box aren’t something that can be given up. So no matter how much discomfort it can cause, life demands that a cat not stop using the toilet. That said, these affected cats will tend to be more likely to ‘hold it’ for longer then they might have before. And because of this, we may see sometimes see harder feces being produced, which in turn are more of a strain to pass.
The main areas I would be worried about discomfort would be his back, hips, and back legs. And it is possible that if this is mild or moderate, that these litter box signs might be our only hints and the only time we can appreciate that he isn’t feeling 100%. And it is understandable, because if you imagine, passing feces requires significant forces on the body, which they do while balancing on pebble like litter, while standing on two feet. Often in cats with back pain or arthritis, this can be a bit much. And this is when they just decide that it is easier to go outside the box (especially when beds are softer, have more grip, and are free of the pebble like texture that litter has). For some cats this will then become an all the time occurrence, while others will just do it intermittently (when they can't be asked to deal with the box).
Therefore, because your kitty is older and this is likely playing a role in what you are seeing, I would also consider speaking to he vet about the trying him on a cat-friendly anti-inflammatory (even just a small dose to see if this helps) like Metacam. They will also be able to have a feel of his joints and back and let you know what his orthopedic situation is at his age.
Alternatively, you may consider trying glucosamine/chondroitin supplementation with your cat. This is a nutrient supplement that is available at your vets, pet shops, and health food stores (as capsules, liquids, and even treats). It works by aiding joint suppleness by helping cartilage replenish itself and blocking enzyme destruction of cartilage in the joint. Often we can find this helpful in animals with mild signs, but it might be enough to take some of the discomfort away from him and help him to comfortably use the litter box. Normally we give kitties 50mg glucosamine + 15mg chondroitin a day per 10 pounds of body weight. So, do consider trying this with him.
As well, you do want to make an effort to avoid this becoming a habit for him. So do make sure that you are thoroughly cleaning the areas he has used with an enzymatic odor neutralizing cleaner (LINK1 LINK 2). This will ensure that the smell will be eliminated for both you and Fluffy.
In the meantime, do consider trying a litter box that has a lower lip, so that he has no difficulty getting into the box. As well, if you did make any changes to his box (litter type, brand, scent, or location of the box), this should be restored to his previous accepted default. But if he is still urinating in the box, litter box based issues are less likely. And of course, if you are concerned that he is 'forgetting' where his box is, do try a litter attractant as a reminder. (you can even put a box in the other places he may be going).
Overall, inappropriate elimination can be caused by a range of issues. Still, if this has been sudden onset without changes to his feces, box, or household; then this would be our main concern for Fluffy. So, do consider the above steps to help address this for him and remove any reluctance he may have for the litter box.
I hope this information is helpful.
Please let me know if you have any further questions.