When it comes to telephoto or long-focal-length zooms... "if you wanna play, you gotta pay".
You can get cheap 70-300mm lenses but I think you'll get mediocre results. You'll also find lenses getting slower (high F-stops) unless you really dump some money into it - and you have to expect those lenses to get fairly pricey, too.
I picked up an ~30-year-old Vivitar 400mm F5.6 lens late last year, it's a Pentax screwmount so you need a small adapter to use it on the K-mount bodies - ie, every Pentax for the past few decades. $90 for the lens, ~$25 for the adapter, and away I went. Quality is OK, it's reasonably sharp but the colors are a little dull (I posted a couple shots in the zoo thread that YEKCIM starts a week or two ago), and it's big and heavy and kind of a pain to focus correctly.
You can keep an eye on eBay to look for used lenses floating around... a telephoto prime will probably be your best bang for the buck. A K-mount Vivitar that looks identical to mine just sold for $185 w/shipping - maybe I should sell mine and see if I can make some money.
But a Tokina 400mm F5.6 (with autofocus) sold on a Buy-It-Now for $464 - like I said, you gotta pay if you want to play.
You also may want to check local camera shops to see if they sell used lenses. My Vivitar came from a local little tiny camera consignment shop that is stuffed with old stuff, usually for a decent price.
Pentax does have a 300mm F4 lens on their roadmap for September, but I don't know anything about price. Generally, Pentax makes exceptional primes so I'd expect good things from it. It's also a DA (digital) lens, so it will probably be smaller and lighter than a 300mm designed for 35mm. They also have a DA 55-300mm coming later, and a DA* 60-250mm F4 targeted for December - the "*" is their top-line stuff, like Canon's "L", and this will probably be quite an expensive lens.