In reply to Lyndsay Superclimber:
I'd agree with Duncan Bourne about Starigrad being the obvious place to stay for Paklenica - otherwise you'd have a fairly long drive each day. The beach is not a classic sandy beach, but the water is clear and warm - the best stretch of 'beach' is outside the Restaurant Dalmajia mentioned above (also the best fish in town, although there is a small restaurant just east of the Ante Steakbar that does a more home-cooked version of a similar menu).
The Paklenica Buffet (Restaurant Dinko, run by one of the early pioneers of climbing in Paklenica) is the equivalent of Pete's Eats, frequented by climbers, and is at the entrance road to the Park.
By the way, if you don't already know this, you have to buy a climbing permit for the park - one, three or five day passes, 150 kuna for 5 day pass,which doesn't have to be used consecutively. Sundays used to be free, but not now.
Its a spectacular place to climb - grades can be harder, or occasionally easier, than you might expect.
Dave