The key difference between Saul and David is loyalty (trust, faith, belief, understanding, obedience, humbleness).
Saul had attacked the Philistines. Samuel told him to wait 7 days and he would arrive. Saul saw the enemy gathering against him, panicked, forgot the promise of God, and turned away to formulate his own "work". Samuel shows up right after Saul sacrifices.
1 Sam. 13:13-14 And Samuel said to Saul, Thou hast done foolishly: thou hast not kept the commandment of the LORD thy God, which he commanded thee: for now would the LORD have established thy kingdom upon Israel for ever. But now thy kingdom shall not continue: the LORD hath sought him a man after his own heart, and the LORD hath commanded him to be captain over his people, because thou hast not kept that which the LORD commanded thee.
God had promised him to reign, but Saul failed to believe. David, however, did believe God (was a man after His own heart; Acts 13:22).
The end of the matter is this.
1 Sam. 15:22 And Samuel said, Hath the LORD as great delight in burnt offerings and sacrifices, as in obeying the voice of the LORD? Behold, to obey is better than sacrifice, and to hearken than the fat of rams.
PS. Re Romans 11:29, the preceding verse sets the context; that is, concerning the gospel, concerning the election.