Hi, Angliholic. I would say that "fell downstairs" is closest to "fell down the stairs." Similarly, you could say "Tom ran downstairs " or "Tom ran down the stairs." In each pair, "downstairs" emphasizes the result (he was upstairs, now he's downstairs) while "down the stairs" emphasizes the process and the actural physical stairs (he ran down the old, rickety stairs).
As for "Tom fell down from the stairs" or "Tom fell down from the sky" -- I wouldn't say they're actually incorrect, but "down" is redundant -- when people fall, then generally fall down, not up. (Although I suppose that if you were walking up the stairs and tripped, you could manage to "fall up the stairs.") If there is some other description of the location of the falling, you don't need "down."
Tom fell. (okay by itself)
Tom fell down. (also okay --adds a bit of emphasis)
Tom fell off the chair/porch/roof (okay)
Tom fell down off the chair/porch/roof (redundant)
In "Tom fell down the stairs," you need "down" because the location of the falling is "down the stairs." You can't just say "Tom fell the stairs." (But you could say "Tom fell on the stairs." That would suggest that he fell, but ended up sitting or sprawling at about the same place on the staircase as he was before he fell, not lower down.)
Does that help?