Oddly enough, it seems that after all the discussion at this post, no-one actually wrote down a criterion for a nilpotent matrix to have a square root.
The answer is very nice, in fact:
Proposition. A nilpotent matrix has a square root if and only if the -th Jordan block (from largest to smallest) is the same size, or one larger than -th.
Who feels like giving a proof in comments?
EDIT: I originally bollixed the condition, by transposing the partition given by the Jordan blocks (the above condition is the same as the partition given by the Jordan blocks having transpose where each odd row length appears at most once).