Recommendations come in late all the time. It probably won't make any difference.
I agree.
It actually makes your referees look worse than it ever could you.
Rarely, the non-arrival may delay action on your application (sometimes, there needs to be the official "trip wire" of all documents in before the candidacy is officially "alive."). If there are a huge number of applicants, this could result in your application not being read/reviewed (it "shouldn't," but when details are sluffed by search committee members, this is one of the prime ones).
Most likely, though, if the committee has reviewed your partial portfolio and liked you, but need, for some internal policy reason to have a completed application before they can "officially" act on your request, they will contact you (and you then forward this contact on in some way to the delinquent referee(s). S/he, hopefully chagrined, responds immediately.
Your particular case seems that all documents are "in." It _might_ (maybe, possibly, could be) a problem if (and pretty nearly only if) there is some internal policy that would have weeded you out. Most likely, there isn't (inside academy perspective; you'd be surprised how often this happens - even for job applications for tenure track faculty); savy committee members know this could happen. Sometimes (sometimes), faculty are constrained by idiot policies from idiot HR people. Generally, though, they are not (or they deliberately plan around such policies with an arbitrarily early "deadline" date).
Most likely, the deadline for applications was a bit fake. The actual selection review would very likely not occur for a week or two after the posted deadline (in other words, the actual decision makers wouldn't even be looking at documents for days). It's possible they may never even know any of your documents were "late." Don't count on this, by any means (in the future), but also don't panic (at present).
It would be more of an issue if you, personally, had not sent something (say, an application essay, etc.).
So, in sum: 1. yes you are right to be concerned. 2. yes, you were absolutely correct to contact your referee (and you are completely in the right). 3. Don't panic. It likely didn't hinder your application. 4. For the future, mark the tardy professor. If this is a pattern, factor that in to your future plans regarding his/her recommendation. You may have no choice (because s/he is so strong, appropriate, or singular). But, when you do . . .