Palutena's kill options aren't as bad as those %s look, as rage and stage positioning are a big factor, especially due to Palutena's style. Also, what redcap said!
jab -> utilt scales tremondously with rage.
If you are at 125% and they are sheik on T&C they will die at 110 before utilt.
Upthrow will kill at 120 with same conditions.
Utilt, upthrow, and upair are your "guaranteed kill moves" past a certain %, not only because they hit them vertically (less based on stage positioning) but because the knockback scales hard and "guarantees" a kill past a certain %, even if a bit staled.
With good rage (100-150), utilt will kill at 120, upthrow will kill at 140, upair will kill at 100 (normal stage height like smashville and FD).
Bair and fair are kill moves that don't have high scaling, but will kill at higher %s mostly based on positioning. For example, if you have 125%, bair may not kill at the center of the stage even at 150%. But if you ledge trump them, they can die at 90. Similarly, fair will not kill at the center of the stage until about 180%, but at the ledge it will kill at 120 (this is a really nice number, thank you 1% damage buff -- before hand it was like 140, that 1% really did a lot in the knockback calculation). Really though being able to kill with dthrow -> fair at 110% before grabs/pummels at the ledge is really nice (in case upair doesn't combo some reason). It is a true combo.
Upsmash vs dsmash: upsmash is almost always better, except in cases where you have no or almost no rage, in which case dsmash can be slightly slightly better (the tip of dsmash, which sends horizontally, can kill a few % earlier if at the edge), because upsmash has more BKB which is affected by rage, but dsmash has a high KBG.
Dsmash(sweetspot, diagonal trajectory) kills at 115 without rage, 95 with 125 rage.
Dsmash(tip, horizontal trajectory, at ledge) kills at 95 without rage, 80 with 125 rage.
Upsmash kills at 100 without rage, 80 with 125 rage.
Fsmash vs dsmash: fsmash is always better regardless of sweet or sourspot, stage positioning, and rage. Perhaps the only situation where you should dsmash over fsmash is if you would be fsmashing him across the stage, in which case a dsmash's sweetspot diagonal trajectory would be better, but in that case you should just upsmash.
Fsmash kills at the ledge at 80% without rage, 65% with 100% rage.
Fsmash kills at the center at 100% without rage, 85% with 100% rage.
Fsmash kills at the opposite side at 140% without rage, 110% with 100% rage.
Fsmash is one of those attacks that rely a lot more on horizontal positioning, thus rewarding stage control and hard reads.
Other moves to consider:
Bthrow kills at the ledge at 150% without rage, 135% with 100% rage. Without proper DI or if they don't react fast enough, bthrow can kill at 110% with 125% rage. Dtilt kills at the ledge at 130% without rage, 110% with 100% rage.
Nair off stage (edgeguarding) will kill at 120-140% depending on rage.
Nair on stage will kill at 140-160% depending on rage and stage positioning.
Ftilt kills at the ledge roughly 125-150 (?).
Fthrow kills on short horizontal blastones (SV) at the ledge at 150% (rage insignificant) if they DI away expecting you to dthrow -> fair, or if they are trying to DI your upthrow away from the stage. Unfortunately this will be very situational, but still something to consider (if only fthrow scaled slightly harder, it would be a real threat and further compliment her scary grab/mixup game, and reward stage control even more, but instead she has a very mediocre fthrow game). If they react to this and know they may die, if they stop DI'ing away during the flight (even if they were DI'ing away when the fthrow occured) then they will not die, unless perhaps at even higher % (in which case you should just upthrow, unless you have no rage to do so since upthrow with no rage won't kill until ~180, but a fthrow with mis-DI may at 150).
(Numbers based on average weight, like Marth, and based on average blastzones).