I used to support the color laserjet 4500, which is basically the same printer you have, except your printer is a bit faster, having a newer formatter board.
The printers are designed to work until the cartridge is nearly out of toner, I think the 20% mark they quoted was not given to you clearly or they misunderstood it. At about 20% left, the printer flags a warning telling you the cartridge is low, thus giving you time to spend all that money on a new cartridge. However, the printer will still print until it detects a cartridge empty condition, when there is a minimal amount of toner left in the cartridge. If I remember correctly, warranty seldom covers replacing a cartrdige if it is in this low state, since in HP’s view you are about out of toner anyways.
Most of the pages per cartridge calculations are done based on a coverage rate of 5% per page - however this is usually a bit on the low side from my experience, especially with color printers.
As an aside, both of the problems you are having are very common. The carousel design of the cartridges on the 4600 series is prone to toner leakage. Color carts usually leak more than black because there is little magnetic material in the toner which helps it adhere to the various rollers in the cartridge and during the transfer process.
It has been a while since I have troubleshot these, but the black marking on the top of the page could be the black toner, but it can also be caused by a clutch failing that moves the transfer belt. If a new toner does not fix it, it will likely require some repair. The other possibility is you have a buildup of toner inside the printer, from the leaking cartridge(s). You can try some cleaning yourself by pulling all the consumables out and using a lint-free cloth with a bit of rubbing alcohol or warm water. If you get toner on your clothes, be sure to wash them in cold water as warm water will set the toner and make it impossible to get out.
As far as the manual tray goes, there are few replaceable parts there, and worst-case I believe it required a new middle drawer assembly, because there is a clutch and motor that can fail there. They are pretty expensive, IIRC. Best case is that your rollers are worn only. You can get a bit of life out of them, if this is the case, by roughing them up a bit with a nail file. But you would need new rollers as eventually the rubber gets a bit too hard to reliably pick up pages.
The 4600 does not have a really robust manual feed, it scews the page quite a bit and is not built to be used a lot.
If you have any other questions about this printer, just reply to the thread. It has been a while, but I have taken these things apart down to the frame and put them back together again many a time!