This is a common problem that I've come across myself many times. I ended up going down the "just use a number for the id" route, meaning it's not quite as ugly to the clients to see those UUIDs.
The only other way, as you already eluded to, is to hide that ID behind some kind of query, which you'll have to feed parameters to in order to retrieve the correct UUID, however, that means you may as well be using those parameters as the primary key for table!
I'd say there's no way to do REST (i.e. state transfer of an model) without being able to identify the instance you're RESTing, so you're going to need a key, whatever form that key takes.
If your concern is due to security, I see the problem as is in your server message validation code, not that the client sees Ids. If a hacker wants to load some data from your table, they won't need to ids to do so. And you ought be validating the requests too, so no dodgy stuff comes through to your business layers anyway, i.e. Authentication and Authorisation of messages.
To come back to your question:
"accessible through REST, so I don't want to expose the primary key"
I think that it's the opposite, you NEED to expose the primary key in order to do REST.
EDIT: As @Murph pointed out, it actually DOES give attackers a better chance if you give Ids to the client - I did not know this. It may be that other answers here (I'm looking at the shortest one saying to encrypt the key) may be more correct to your situation. Edit 2: Seems UUIDs are no safer than ints...