How to protect the 'public' part of a REST service from spam?

While the app-specific code is a good idea for a first line of defense against spam, you should still implement some rate-limiting on any services you are concerned about.

For example, if you use sessions on your REST services, you can easily rate-limit the number of calls you process from a single session. The session doesn't have to be authenticated at all and is only used to identify a single client while they are making requests. A simple redirect back to the requested service if they try to connect without an open session is all that's needed, and virtually all web frameworks or stacks have this built in.

You can also rate-limit on other properties, such as IP or user-agent fingerprint, but those are less reliable than a session-based method.

In general, a common approach is the API Key, which is the same as the secret-token you describe above. You can hardcode this into your application and make it difficult for someone to reverse engineer it (hide it, build it up from various parts stored at different places within your application, etc). You are correct in that a determined attacker will be able to recover the key (if your app can do so, someone else with access to your app can as well)...but you can make it more difficult where, hopefully, it wouldn't be worth the time and effort to do so.

You could also look at deploying mutually-authenticated SSL, so that your server will only accept incoming connections from your app and your app will only communicate with your server.

Here's the high-level approach. Create a self-signed server SSL certificate and deploy on your web server. Then create a self-signed client and deploy that within your application as a resource. Configure the server to require client-side SSL authentication and to only accept the client certificate you generated. Configure the client to use that client-side certificate to identify itself and only accept the one server-side certificate you installed on your server for that part of it.

If someone/something other than your app attempts to connect to your server, the SSL connection will not be created, as the server will reject incoming SSL connections that do not present the client certificate that you have included in your app.

This is truly old, but there is something you can do. I would create a time-based secret token. Something that expires in seconds that you can send along with the request. Since your iOS app source code isn't public, it's just up to you to keep it secret. You need to ensure that your time is synced between the app and the server. You can send the time from the mobile app to the server and calculate an offset (if there is one). This will prevent anything other than your app from talking to your API before you're authenticated.

Base the secret on something that is unique to the phone and only you would know what that is. That uniqueness would also have to be known on the server side.