How to add of story-telling elements to increase player satisfaction?
I think that's what the board game has been lacking for me and several other dedicated players; a cohesive story of what we are up against and what we are trying to accomplish.

This surprises me, since Eldritch Horror is usually praised for creating a cohesive story through the three Mysteries that you have to solve to defeat the Ancient One, creating a sense of progression and a beginning, middle, and end to the story.

I think all the players of the board game would get inspiration and a moral boost if they knew in detail what they are up against, and what it would mean for the hamlet of Dunwich should we fail. I think this holds true for other aspects of the game (i.e. the destinations, the ancient ones, other monsters, and certain items).

I think this is your real problem: a lack of knowledge, or immersion, in relation to what is going on in the board. Fortunately, there are several things you can do to help that (but keep your expectations in check; Eldritch Horror will never have as strong or cohesive a narrative as something like Time Stories).
For what it's worth, I think that Arkham Horror is better at solving this problem, but we're talking about Eldritch Horror now.
Read the cards aloud
This may seem like a no-brainer to some players, but I have played with people who draw a location card, read it silently, roll some dice, then say that they need a Common Item. That is beyond boring and disconnects everyone from what is going on. Reading the cards aloud adds to the atmosphere and increases enjoyment for everybody.
Also, there are ways to increase the drama as you read. I don't recall if this is an official rule or not, but when I played in a game with one of the designers, he said that every time it says &quot;Make a  roll&quot; or similar, he intentionally made it so that they always ended a sentence. While reading, he said you should stop as soon as you read that sentence, make your roll, and then continue reading. This helps immersion by leading to anticipation as to what will happen. Some players even prefer to have other players read the card to prevent players from silently reading ahead.
Start your game with one of the descriptions in the rule book
The rule book for the base game and each of the expansions has a brief paragraph from someone in-universe describing the the general atmosphere of the threat, and this can be helpful for setting the tone for players. If you see other things like this, read those too.
Read descriptions from Lovecraft's works
Say that your Ancient One is Azathoth. You might choose to at some point read a quote from The Dream Quest of Unknown Kadath:

[O]utside the ordered universe [is] that amorphous blight of nethermost confusion which blasphemes and bubbles at the center of all infinity—the boundless daemon sultan Azathoth, whose name no lips dare speak aloud, and who gnaws hungrily in inconceivable, unlighted chambers beyond time and space amidst the muffled, maddening beating of vile drums and the thin monotonous whine of accursed flutes.

Lovecraft had a gift for describing things in a way that evokes a specific emotion. Reading these quotes helps convey that to the players, and also educates them if they are unfamiliar with that being.
Do this with whatever you feel is appropriate. I don't know that there are any evocative passages on shotguns, but you might read one when the Necronomicon is revealed.
Read descriptions you write yourself
I once played a game of Eldritch Horror's sister game, Arkham Horror, where the first time a player entered a location, the game owner read descriptions of the places, which he wrote. For instance, when I went to the Graveyard, I was told that I saw graves of veterans from the Great War (i.e. World War I), but one of the graves I passed was old, yet recently dug up. I then read the encounter as normal. This could be done with Eldritch Horror too.
Invent your own rationalization and connections
Why did I get a book from a random dude on the street in Cairo? Maybe I saved their life from the zombie I just killed and they gave it to me in thanks. Just let your players run with it.