K-mount compatibility is unsurpassed... with the exception of Pentax MZ-30/50/60/*ist film body, your K lenses will fit on any other Pentax bodies and will work just like how it works on your M-series bodies.
A good replacement M-series body may be hard to find... Fotographix at Lucky Chinatown has 2 MXes, one of which is near mint. They've also got a nice LX. The price is on the high side though I must admit they are beautiful. Sometimes Prime Camera and Camera Workshop carry used Pentax cameras. There's another shop on the 2nd level of Pennisular Plaza that displays some nice Pentax cameras. I forgot its name.
Alternatively, get a new MZ-5n or MZ-3. These are modern bodies with a clean, classic layout. All settings are done via dials and switches, not menus. The only difference between MZ-5n and MZ-3 is the different shutter mechanism - MZ-5n x-sync at 1/100 with top speed 1/2000, MZ-3 x-sync at 1/125 with top speed 1/4000.
With the digital SLR body due for release in August, you can mount the K lenses onto it and it'll work just like how it works on your M-series bodies... beautiful, isn't it?
Note the name for the DSLR though. It's the *ist
D, not *ist. The Pentax *ist is another budget entry-level film SLR.