Can I counter a creature by invalidating the target of its “comes into play” effect?
Easy answer is the second scenario you propose. Akoum Boulderfoot's ability is a triggered ability, with the trigger for the ability being 'Akoum Boulderfoot has entered the battlefield'. Targets for spells and abilities are chosen when the spell or ability is put onto the stack. Triggered abilities do not go on the stack until the trigger for the ability is true. Permanents are not actually on the battlefield until the spell resolves.

Answer to your primary question though is no, you can't counter a creature by invalidating the target of its 'come into play effect', due to the come into play effect not going on the stack until the creature has fully resolved.