Right, given that each appearance of the Legion of the Damned in the rules has been different (in Codex: Ultramarines, they're just Fearless, Fear-causing Veteran Space Marines... later versions gained the 'appear from thin air' quirk, leading to the current version which is heavily supernatural), I've put together something I feel to be reasonable. I can't actually find my copy of Codex: Space Marines, so I'm going from memory on a few things, and thus a couple of things might be incorrect... they've very much a spur-of-the-moment rough job.
Now, enough of my pre-emptive excuses...
Damned Legionnaire (Elite)
WS BS S T Ag Int Per WP Fel
55 55 55(12) 55(10) 50 50 50 60 50
Movement: 6/12/18/36; Wounds: 30
Skills: Awareness (Per) +10, Climb (S), Dodge (Ag) +10, Common Lore (Adeptus Astartes) (Int), Common Lore (Imperium) (Int), Common Lore (War) (Int), Concealment (Ag), Drive (Ground Vehicle) (Ag), Forbidden Lore (Warp) (Int) +10, Intimidate (S) +20, Literacy (Int), Navigation (Surface) (Int), Scholastic Lore (Codex Astartes) (Int), Silent Move (Ag) +20, Speak Language (Low Gothic) (Int), Speak Language (High Gothic) (Int), Tactics (Assault Doctrine) (Int) +20, Tracking (Int)
Talents: Ambidextrous, Astartes Weapon Training, Bulging Biceps, Crushing Blow, Duty Unto Death, Hatred (Chaos Space Marines, Daemons, Mutants, Xenos, Heretics), Lightning Attack, Lightning Reflexes, Mighty Shot, Strong Minded, Swift Attack, , Heightened Senses (Hearing, Sight), Killing Strike, Nerves of Steel, Quick Draw, Resistance (Psychic Powers), True Grit, Unarmed Master
Traits: Astartes Implants, Auto-stabilised, Fear (3), From Beyond, Incorporeal, The Stuff of Nightmares, Undying, Unnatural Strength (x2), Unnatural Toughness (x2)
Weapons: Astartes Bolt Pistol (35m; S/2/—; 2d10+7 X; Pen 5; Clip 10; Rld Full; Tearing, Reliable), Frag Grenades (36m; S/-/-; 2d10+2 X; Blast (5)), Krak Grenades (36m; S/-/-; 3d10+6 X; Pen 6), Combat Knife (1d10+14 R; Pen 2) and one of the following:
• Astartes Bolter (100m; S/2/4; 2d10+7 X; Pen 5; Clip 28; Rld Full; Tearing, Reliable)
• Flamer (30m; S/-/-; 2d10+4 E; Pen 3; Clip 6; Rld 2Full; Flame)
• Plasma Gun (90m; S/2/-; 1d10+11 E; Pen 6; Clip 20; Rld 8Full; Overheats, or 100m; S/2/-; 2d10+11 E; Pen 8; Clip 20 (3x ammo use); Rld 8Full; Overheats, Recharge)
• Meltagun (30m; S/-/-; 2d10+10 E; Pen 13; Clip 5; Rld 2Full; +1d10 damage at Short Range)
• Heavy Bolter (120m; -/-/10; 2d10+12 X; Pen 6; Clip 60; Rld 2Full; Tearing)
• Heavy Flamer (30m; S/-/-; 2d10+8 E; Pen 6; Clip 10; Rld 2 Full; Flame)
• Lascannon (300m; S/-/-; 6d10+12 E; Pen 10; Clip 5; Rld 2Full)
• Missile Launcher with Frag (250m; S/-/-; 2d10+6 X; Blast (6); Clip 1; Rld Full) and Krak (250m; S/-/-; 4d10+10 X; Pen 12; Clip 1; Rld Full) Missiles.
• Multi-Melta (60m; S/-/-; 4d10+12 E; Pen 16; Clip 10; Rld 2Full; Blast (1); +1d10 at Short Range)
• Plasma Cannon (180m; S/-/-; 3d10+12 E; Pen 8; Clip 24; Rld 2Full; Overheats, Unreliable, Blast (1)) or (190m; S/-/-; 4d10+12 E; Pen 10; Clip 8; Rld 2Full; Overheats, Recharge, Unreliable, Blast (3)) on full power.
Armour: Astartes Power Armour (Body 10, Heady 8, Arms 8, Legs 8)
Wrath Incarnate: The Legion of the Damned seems to be little more than a spectral manifestation of the Emperor’s Wrath. The Legion of the Damned, in spite of the Incorporeal Trait, may attack and damage enemies normally. In addition, Damned Legionnaires do not track ammunition expenditure and need never reload. However, not being entirely intangible, any attack that hits by more than two degrees of success will strike true and be able to deal damage normally.
Yeah, they're terrifying... extremely difficult to stop by conventional means, fear-causing, mobile and possessed of considerable firepower backed up by great skill. But that's the point. The Legion of the Damned turn up when the Imperium would otherwise be utterly screwed, and thus they need to be powerful enough to make a difference during those epic end-of-mission conflicts where the group have burnt a half-dozen Fate Points already and still may not triumph.