Well, you could always try Ryanair's new so-called Hamburg to Frankfurt service (due to start next week)... Ryanair's "Hamburg" is Lübeck which is actually quite convenient for Warnemünde... but their "Frankfurt" is Hahn which is in the middle of nowhere, about two hours from Frankfurt. I suspect you'd probably have most of the aircraft to yourself because I can't see many people flying between LBC and the middle of nowhere.

If I were you I would seriously look into taking the train to FRA... I doubt you'd be saving a lot of time flying from Hamburg or Berlin, by the time you've travelled there and gone through all the usual airport hassle. Journey time from Rostock to FRA (i.e., direct to the airport) is six hours, with another 20 minutes or so to get into Rostock from Warnemünde.