Start with tool use. It may be that non-sapient animals use tools (however, the 'sapience' of tool using species may be reevaluated as our understanding changes). It may be you have sapient beings that do not, for whatever reason, use tools. However, it should be a relatively visible criteria to start you off - and I would suspect very strongly that you'll need more than one criteria anyway.
Any tool-using species should then be put on a "maybe" list for further evaluation (and I second a4android, tool using plants get a "yes" from me) - and depending on relative abundance of terraformable planets, maybe that planet or at least the relevant habitat should be avoided anyway - because even if they are not sapient, they might still become so, at some point. When it comes to ethics, a few false positives (protecting a non-sapient species) is far preferable to even one false negative (that would be effectively genocide of a sapient race)... and it's a lot easier to go back and terraform later, than to undo the process if you were wrong.
Maybe the next criteria would be alteration of the environment - obviously the more 'unnatural' the alteration, the easier to find and evaluate. Maybe something like bird's nests doesn't qualify, but maybe the more elaborate construction of termite mounds will make them worth a second look. Beaver dams fall somewhere between. Or moving from benefiting from fires to using embers from one area to start new fires (unsubstantiated, but the idea is there) in a different one. Actually, I'd put any fire-using species on the 'maybe' list anyway, its a pretty dangerous thing to use.
A third criteria you might want to look at it communication - if there are analyzable long-distance signals, that again becomes a reason to go on the 'maybe' list. If they're unusual to the planet's wildlife, or 'unnatural', that might be worth some extra consideration - for example, if the animals use sound and scent, then drawn pictures might be worth a second look (or radio waves, but you said stone age). Also, most animals will want to communicate at a relatively short range, since they're concerned with their immediate surroundings, so something broadcast over half the continent away is worth looking into (relay towers, beacon fires?). Any obvious signs of organization - especially large scale organization, or coordination and cooperation between separate groups, should draw your attention for a second look.
And on that note, cooperation between species should also be worth a second look - it can signal compassion (protecting vulnerability even in other species) , or domestication (putting other species to work). You might get some false positives from animals who developed symbiosis, but probably the more similar the species are, or the more the relationship costs either, the more I would think it likely to be the action of sapient beings. If the species is after similar resources (like both hunters) cooperation is more difficult than if the species are specialized and non-competing; likewise if a species is taking actions that benefit the other but cost the first in time or energy (driving off predators, caring for injured), it seems more likely to be reasoned than pure instinct, as opposed to actions that simply happen to benefit both (feeding off of parasites).
So now you have a few criteria for a shortlist, how to evaluate further? Go in person, and study a lot more closely. Check to see how these species react or adapt to something new, if you can find any kind of mutual communication, how these species will react to an alien presence (er, that's you). Take environmental factors into consideration, as much as you can - how much their behavior is different from other similar species on that planet, how much is taught as opposed to instinctive, or how much might be reasoned and how much reactive, and so on. As a bonus, you might make a final communications check by visiting the planet directly, and wandering about for a bit - the better to see if anyone tries to communicate with you.
Then you've got your planets all lined up - some with nothing concerning, some that are still 'maybes' - with a probably sliding scale of maybe-just-animals to likely-to-be-sapient, and some where you will definitely want to say leave it be and find a new planet. Depending on how many planets are capable of being terraformable, and how much stock your culture puts into preserving diversity and preventing extinctions of even animals, your organization might be happy crossing off all the 'maybe' planets, or might only protect the really truly likely ones.