The printer may need servicing but try the following steps first:
First, make sure there is a toner cartridge installed in the printer. If not, this can result in a false out of paper error condition. You should also try another toner cartridge in case the plastic tab on the cartridge (which tells the printer the cartridge is installed) is broken.
Next, if you are trying to print from the cassette, try printing from the multipurpose tray instead. If the printer pulls from the multipurpose tray without a problem, make sure you have the cassette properly configured and installed.
Take the cassette out, reseat the paper and make sure there are no obstructions inside the printer where the paper rests.