What is falling short of grace
Grace refers to a completely unearned gift. And the only way you can "fall short of grace" is to not accept grace but to try to earn the gift. This is done by observing some law, regardless of what that law is.
Paul discusses this in Romans, contrasting gentiles who accepted grace, with jews who did not, because they could never get past the observance of the law as something that established their righteousness:
Romans 9:30–32 (KJV 1900)
What shall we say then? That the Gentiles, which followed not after
righteousness, have attained to righteousness, even the righteousness
which is of faith.
But Israel, which followed after the law of
righteousness, hath not attained to the law of righteousness.
Wherefore? Because they sought it not by faith, but as it were by
the works of the law. For they stumbled at that stumblingstone;
Thus those who sought righteousness by the law did not attain, but they stumbled. Paul calls this a "stumblingstone" and elsewhere, "the offense of the cross", and what he means is the idea that one's sincere efforts at trying to be a good person not only fail, but are an enemy of grace.
Obviously this offends someone who spent their life trying to observe the law much more than someone who understood they could never observe the law. Therefore the gentiles accepted grace but the jews did not.
Paul continues, lamenting Israel's inability to stop trying to rely on their own righteousness:
Romans 10:1–3 (KJV 1900)
Brethren, my heart’s desire and prayer to God for Israel is, that they
might be saved.
For I bear them record that they have a zeal of God,
but not according to knowledge.
For they being ignorant of God’s
righteousness, and going about to establish their own righteousness,
have not submitted themselves unto the righteousness of God.
Thus attempting to establish their own righteousness means they are rejecting grace, and therefore are not submitting themselves to the righteousness of God. It amounts to saying "the sacrifice of the cross is insufficient".
That is a big deal.
Falling short of grace in the church
But even among believers, preachers started appearing insisting that God's grace needs a little push from them. Thus a large proportion of Paul's epistles were spent swatting away all those teachers who would show up after Paul left and start explaining to the new churches that "yes, you are saved by grace, but you do understand that God helps those who help themselves, right? So you still need to observe X" and that's why Paul had to keep writing these passages, e.g. to Colossians:
And you, being dead in your sins and the uncircumcision of your flesh,
hath he quickened together with him, having forgiven you all
trespasses; Blotting out the handwriting of ordinances that was
against us, which was contrary to us, and took it out of the way,
nailing it to his cross; And having spoiled principalities and
powers, he made a shew of them openly, triumphing over them in it.
Let no man therefore judge you in meat, or in drink, or in respect
of an holyday, or of the new moon, or of the sabbath days: Which are
a shadow of things to come; but the body is of Christ. Col 2.13-17 KJV
Falling short as failing to enter the rest in Hebrews
Hebrews also talks of "falling short" (ὑστερέω) earlier, in chapter 4
Hebrews 4:1–10 (KJV 1900)
Let us therefore fear, lest, a promise being left us of entering into
his rest, any of you should seem to come short of it.
2 For unto us
was the gospel preached, as well as unto them: but the word preached
did not profit them, not being mixed with faith in them that heard it.
3 For we which have believed do enter into rest, as he said, As I have
sworn in my wrath, if they shall enter into my rest: although the
works were finished from the foundation of the world.
4 For he spake
in a certain place of the seventh day on this wise, And God did rest
the seventh day from all his works.
5 And in this place again, If they
shall enter into my rest.
6 Seeing therefore it remaineth that some
must enter therein, and they to whom it was first preached entered not
in because of unbelief:
7 Again, he limiteth a certain day, saying in
David, To day, after so long a time; as it is said, To day if ye will
hear his voice, harden not your hearts.
8 For if Joshua had given them
rest, then would he not afterward have spoken of another day.
9 There
remaineth therefore a rest to the people of God.
10 For he that is
entered into his rest, he also hath ceased from his own works, as God
did from his.
Here, Hebrews is explicitly making the analogy of "sabbath rest" - which is the distinguishing characteristic of Judaism, with "grace", which is the distinguishing characteristic of Christianity -- in that one ceases from their own works.
In the law there is a death penalty if you work - even if you gather sticks to light a little fire - because even the smallest effort meant that you had not ceased from your own labor.
Those who do not cease from their own attempts at establishing righteousness therefore fall short, and do not enter into God's rest.
This happens because of unbelief -- not unbelief that God exists, or that God provides, or even that God delivered them out of Egypt, but unbelief that God's provision is sufficient for them to enter the Promised Land. This was the sin that kept the Israelites from entering. Moses murdered a man and escaped justice. And he also struck the rock twice, giving God a little help. One of these prevented him from entering the promised land.
Just as the people in the wilderness doubted that God was sufficient for their needs, the one who attempts to establish his own righteousness doubts the same. In both cases, they do not cease from their own labor and so fall short of God's grace.
