The sentence is problematic because of the syntax. A reasonable rewrite that retains the superfluous yet would be:
Most importantly, he’s found footprints of dinosaurs that we haven’t yet found bones of.
A more formal and less verbose rendition of this sentence is:
Most important [1], he has found footprints of dinosaurs for which we have not found bones.
[EDIT: But this is too formal and clunky.]
Most important, he's found footprints of dinosaurs for which we haven't found bones.
As of yet is never any good. It's even more verbose.
You can use yet in a brief response to a question such as:
Have you finished your homework?
Not yet.
Then it's perfectly normal English.
[1]: Sorry, I don't like the /-ly/ form here. I think that adjectives shouldn't end in /-ly/ if they don't need to. Words like homely, comely, and unseemly are adjectives that cannot shed their "ly" without becoming a different word, or, in the last case, a non-word. I also dislike firstly, secondly, etc. But this is strictly a personal style preference.