"At least k" might imply that removing more than k nails is necessary to make the picture fall, which is not the case. I think "exactly k" is perfectly clear.
"Exactly k" is not clear because the picture will still fall if you remove k+1 nails. I think it's harder to get clearer than the way it's stated in the paper: "the picture falls whenever any k out of the n nails get removed, and the picture remains hanging when fewer than k nails get removed."
