Your conclusion that the first motor is the most powerful is correct, given those figures. Note that its peak current is 5A, so you'll need quite a substantial motor driver and battery; either a 4-cell LiIon pack with a suitable rating or a car battery. You may find a car battery a useful weight for holding the whole system on the ground!
Looking at the datasheet, while it doesn't lie, it is definitely on the edge of misleading.
Note that the "max power" stated occurs at almost exactly half the unloaded RPM and half the stall current. This is indeed the "max power" point for such a motor, but the datasheet fails to mention that it is also the nominal 50% efficiency point, thus dissipating 12V*68A-337W = 479W in that tiny motor - destroying it, probably in minutes.
(Ideally, exactly half the power would be delivered, about 400W shaft and 400W heat, but the motor isn't ideal).
The motor is probably suitable for 100-150W continuous output and 200-250W short term.
So practically you must operate the motor at the upper end of the speed range, and if the speed falls below (say) 70% of the unloaded speed (or the current rises to 30% of the stall current) then - unless this is strictly temporary, like starting a heavy load or hitting a chilled spot while machining a cast iron surface, you need to cut the current and protect the motor.
Then the question of which side of the torque speed curve doesn't apply - unless the protection has tripped, you should be on the high speed side.
You can get circuit breakers that will allow short-term overcurrent. These are "motor rated" or Class C breakers for the AC motors used in most machine tools. I don't know of anything suitable for 12V DC though. I'd be looking for a 12V DC supply that can be set to trip if its output exceeds 40A for more than a couple of seconds. And as Olin says, if you want to monitor it yourself, measuring the current is definitely the way to go.
Best Answer
Things to ask yourself:
What is my input voltage? AC or DC? Are you running this off of a battery or line voltage or a control or something else?
What am I doing with the motor? Is it for a fan and will be running at one speed for 8 hours a day? Is it for a servo type application? What's the duty cycle?
What is the environment it will be running in? Does it need to be dust proof? Water-proof? Explosion-proof? Will the ambient temperature be 20 C, 65 C or -40 C?
How many hours does it need to run before failure? 5000 hours, 20,000 hours, 50,000 hours?
Your answers to those questions would give me a pretty good idea of the type of motor you need and what its rating should be.
EDIT: In general, sizing a motor is as easy as you suspect. If you know the power you need the motor to output, then you find a motor that is rated for that power. The rated power on the nameplate of a motor is the power that motor can continuously output without overheating. Generally these ratings tests assume that the ambient temperature of the environment is below 40 degrees Celcius. So if you have a motor that is going to be running at a constant torque and speed at a temperature below 40 C, finding a motor is simple. Things get trickier when you have short duty cycles or a duty cycle where the torque changes abruptly or higher ambient temperatures.