Morning, I upgraded about a year ago when, just prior to the K7 coming out - to the K20, from a K100. Its a wonderful camera, has all the functionality and capabilities you can think of. I hope you will be as happy with it as I am.
As for lens suggestions, I have a few. Obviously the kit, the DA 18-55 is very good as kit lenses go. Its light, small and capable. It does a good job. Due to the resolution of the K20's sensor, the version of the kit lens that came with it was the version II. So if you go that rout, look for a version II. Slightly different optic design.
The DA 16-45/f4 would be my first choice. I have one and I do like it very much. It is a high quality lens, very low distortion. Its somewhat of a larger lens - larger than the kit. A constant f4 through out the focal length range. Sharp, wonderful colors, great image quality, great resolution on the K20. Its a reverse zoom design (16mm is zoomed out, with 45mm pulled in). Its a bit wider than the kit which would be good for landscapes. Their price has come down from about $400 to around $250-300 because it is somewhat of an older design, but its still in production. Personally, I would check the Pentax Forum Marketplace. I would have no problems with a used lens from there.
For a longer focal length the DA 55-300 is again an excellent lens that is highly regarded. That said, it runs around $350 and is probably out of your price range now. So, I have to ask - would you consider a manual lens? Tokina has a number of older zoom lenses, manual focusing that are very good, and can be acquired pretty cheaply. The "RMC" tag usually denotes their top quality lenses. I believe that the RMC has been replaced with their "Pro" series.
I am seeing a lot of folks pushing for the 300mm end, so the lenses going out to 200mm or so, are a tad less expensive. You should be able to pick up a good quality 70-200 or 210 for no more than $50.
Since it appears that you are more interested in landscapes than telephoto, these are my suggestions. If it were reversed, I would go with the DA 55-300 first, and then pick up a shorter focal length lens - probably just the kit.
Your Vivitar 70-210 lens is available in a Pentax K mount, and can be had. A lot of folks look for them. There are a couple of folks here on the forum that have them and search for them. I suspect that they will post here. Any way here is some information on the vivitar with the Pentax mount.
Note - Tokina built the Vivitar Series 1 70-210 version 2 of the lens...
Overall, if you can score a Vivitar Series 1 coupled with a 16-45, I think you will be set. I would think you should be able to do this within $50+/- of your target budget.
Hope that helps