You mention three instances:
The latest (but not recent) episode I remember is this vote from June 2016, when the US senate rejected restrictions on sale of weapons to people on the terror watch list.
The no-fly list is not controlled at such a level that it is helpful for this. The false positive rate is much higher than the false negative rate of existing gun laws. For example, Senator Ted Kennedy was on the list for a while. Why? Someone using the alias T. Kennedy had been put on the list. So everyone whose name matched T. Kennedy was then on it.
This is manageable in travel, as there are other options. People who can't fly can still take a train, bus, ship, or car to their destination. But if extended to guns, this would cause two problems. One, gun rights can't be removed without due process, which would make it harder to put people on the no-fly list. Two, there's no easy way to know if one is on the list.
Note that you are also mixing two things. There is a no-fly list which restricts access to planes and a broader terrorism watch list that is basically, we're investigating this person -- let us know if he or she does anything suspicious. The terrorism watch list does not restrict people from flying, only the no-fly list does. This legislation would have banned people on the investigation list from buying guns.
There also are no examples of someone being on the terror watch list and buying guns that were later used in a shooting. It was a solution without a problem.
I remember that also legislation to prevent people with mental health issues to acquire guns was stopped.
I suspect that you are remembering incorrectly. Or that you are remembering a mischaracterization of the legislation. You don't provide a citation, but I'm guessing that you are talking about the Social Security disability ban. That would have banned people on Social Security disability who met certain other criteria from buying guns.
The problem with that is that the people involved do not have "mental health" issues. They have mental disability issues. They're not as a group crazy, violent, or dangerous. They're people who have their Social Security checks sent to someone else because they don't handle money well.
It is possible that the Sandy Hook shooter would have been on this list. It's unclear how this would have affected things, since he didn't buy the guns that he used. They were owned by his mother, who would not have been covered.
You also quoted
But the Democratic-controlled Senate voted against legislation pushed by the president that would have expanded background checks for firearm purchases to gun shows and online sales.
This is the closest to a minimal gun law of the three examples. Currently it is possible for someone to legally buy a gun from another private individual who is a stranger to that person. The Manchin-Toomey bill is presumably the referenced legislation. It would have expanded existing regulations to include transactions between strangers.
Note that gun shows would not have received special treatment under this law and do not receive special treatment now. The vendors at gun shows are already required to run background checks same as when they are at their places of business. The "loophole" is that if two private individuals meet at a gun show, one can sell a gun to the other legally under the laws for individual sale. It is unknown if this happens frequently, since there is no federal record of such sales.
Completely online sales are illegal now. What is legal is things like Craigslist.org, where people advertise that they either have or want a gun. The actual transaction takes place in person. Again, these individual sales are not covered under existing laws. Or you can make the purchase online and then pick up the gun at licensed dealer. Again, an in-person transaction (and with dealers involved, one that already requires a background check).
This legislation foundered because gun-proponents wanted additional wording to protect buyers from being put in a federal gun registry. Gun-opponents wouldn't sign off on such language, because they thought that it would impact existing registries at the state level. The two sides couldn't reach a compromise.
It's also worth noting that it was not voted down but filibustered. While Democrats may have voted against it, some Republicans voted for it. Overall, in 2013, fifty-four for and forty-six against in the vote.
Note that the general question of why it is difficult to pass gun legislation in the United States has already been asked. That's why I'm concentrating on the specifics of this question and not talking about the more general issue. You can read more about the more general issue at the other question.