it really depends on what you want the lens for. If landscapes mainly, 24 would be my pick, people shots? 31-43-77... you can't beat the trinity...
anyway, be more specific on what purpose the lens would be and you may get more specific answers...
I also shot a lot of outdoor landscapes, waves and rivers. I have to date over 10,00 counts with my K-7. Instead of the kit lenses (18-55 & 50-200), I have the DA18-250mm. The main advantage of the 18-250mm is the absence of lens swapping, but otherwise you have already a similar range..
However I found that the weakness of the kit lenses(& of my DA18-250mm) is the low-light conditions. That is, dusk and dawn. I would recommend you to consider a fast lens (large aperture, low f) like a f1.4 or f1.6.
Large aperture lenses do not come as zoom lenses, but as prime lenses: they are called fast primes.
I have a fast prime Voigtlander Nokton 58mm f1.4, that I bought especially for the low-light outdoor conditions and I can recommend it very, very strongly. (I got the advice from this Forum and I am grateful for the excellent advice.)
The lens has outstanding IQ. It is very solid and sturdy (basically it is WR without the label). Althgouh MF, I set the focus range to infinity as soon as the target is more than 8m away: that is, always for landscape. Simply you do not need to fiddle the focus. Combined with the K-7, the Nokton 58mm f1.4 is a great, great lens for low-light outdoor.
What focal length do you find yourself shooting at the most? Is there anything you find yourself wanting to do that you cant? You seem to have a fairly good range covered with your zooms, however none of them are faster than f3.5. For this reason I'd suggest looking at a fast prime lens. Exactly which length depends on you.
What would you recommend for my next lens?
Would a 30mm or 50mm prime be a good choice? What are the advantages/differences of the two?
Preferences- something with F2, or a better macro focus like .5ft
SDM would be nice... but I've only found $400 lenses with that...
The advantage of 50mm is, all else being equal, you can get a faster lens for considerably less cost. You will be hard pressed to find any 30 f2 lens for $250, but an old 50 f2 lens can easily be found for less than $50. 50mm on APS-C often works well as a portrait lens, less well as a landscape lens. The wider 30mm (or, more realistically, 28mm) is better fit for landscape work.
If you're willing to explore older, used, manual focus lenses, you could easily afford, on your budget, both a fast 50 and a 28mm. The old Pentax M 50/1.7 can sell as low as $50, and it's an outstanding lens, much better than your current Pentax kit lenses. The best of the old 28s (reputedly) is the K series 28/3.5, which usually sells for $125+. It is also an outstanding lens, sharp with superb color rendition. I use one for landscape photography quite often and find it more dependable than even my 12-24.
If you absolutely require auto focus, then you'll only be able to afford either a used F or FA 28/2.8 or a used F or FA 50/1.7.