See Plethoric Pundigrions1 for screen shots showing a version of Microsoft Word (I don't know which one) that for levelheaded suggests correcting it to level-headed and for level-headed suggests correcting it to levelheaded. That should give rise to a frustrating morning of trying to finalize the draft, shouldn't it?
1 Hat tip to Bob Ladd.
You will probably want to know what The Cambridge Grammar of the English Language says about what the right answer is; and those who yearn not just for authority but for actual authoritarianism will be disappointed that it reports, "It is an area where we find a great deal of variation" (p. 1760, in the section on lexical hyphens).
If you think that nonetheless an answer should be stipulated, then go ahead and make up a stipulation. What The Cambridge Grammar is telling you is that you won't have any basis for it. You might just as well have stipulated the opposite. Educated usage will not always match your stipulation (thus showing it to be a good one), and it won't always fail to match.
There are two general tendencies, though. (1) The longer a compound has been in use, the more likely it is to have started being written without a hyphen. (2) American English is a bit less likely to favor hyphenating than British English is. Apart from those two rules of thumb, you are out there working with no net, trying to follow the shifting tendencies in the usage of other people. I think I would recommend simply finding a recent use of the term in the writing of an author whose work you really like to read, and following that. If Stephen King describes someone as levelheaded, and you like reading Stephen King, then write levelheaded. Nothing much will hang on it. Not everyone will agree with you (and Word may even disagree with itself), but hey, it's a free country.
Does that make me sound like an anarchist? I hope not. I believe there are thousands of quite strict constraints on Standard English, constraints such that you would be ill-advised to violate, because you would look like a gormless illiterate. All I'm saying is that whether or not to hyphenate a compound like level(-)headed is not one of the areas of English in which a strict and widely respected constraint holds.
With some misgivings (the above will not make me popular with those who long for stern grammatical parenting) I have left comments open below. But please hyphenate correctly.