Before you even think of painting you will have to wash down all walls and ceilings that have been papered to get rid of all the paste residue as this will react with you paint!
You can negate the need for washing down by priming with zinsser gardz but this is not a cheap option.
The prep needed to bring these surfaces up to a half decent level will take an age and sometimes it is better just paying the money for a re skim. I suppose it depends on how much you value your time and effort and the finish you want as to whether or not you opt for the re skim (which would be my option)!