The earliest time you'll come across a Construct is during the side quest "Out of Body Experience". These guys are pretty tough and you may have a few issues in your earlier levels trying to bring one down at your current level and weapons to hand.

There's a little trick though. Once you've come face to face with one, kill all the initial enemies around him and then die. Once you respawn around the corner, the Construct will no longer build anymore robots. This now gives you the time to kill him without the worry of more enemies being spawned by him and missing out on the achievement.