To quote Wikipedia:
Lovecraftian horror is a subgenre of horror fiction that emphasizes the cosmic horror of the unknown (and in some cases, unknowable) more than gore or other elements of shock, though these may still be present
The hallmark of Lovecraft's work is cosmicism: the sense that ordinary life is a thin shell over a reality that is so alien and abstract in comparison that merely contemplating it would damage the sanity of the ordinary person.
To put this more succinctly - Lovecraft's horror is not in the "jump out and scare" or just another "monster" (like Grendel in Beowulf versus It in Stephen King's story) or gorish scenes, which are all horrifying in their own right. Lovecraft's horror resides in the idea that what the universe truly is is so unlike the lives we lead that comprehending it is its own true horror.
Lovecraft was also a part of the Modernist movement in literature, meaning that his characters are often outcasts or somehow socially isolated (for example, in Kafka's The Trial, no one really explains what is going on to Joseph K.), that the situations they are in are often not fully explained (for example, in Kafka's The Metamorphosis, no one explains how Gregor is turned into a "monstrous verminous bug" - it just happens, in the first sentence in the text), and the monsters are often very surreal (instead of blood, bones, corpses, instead we see slime or tentacles mishmashed in odd ways).
To address the part where you ask "if a horror story had to do with a monster with strange tentacles, this would commonly be referred to as Lovecraftian, but is that just because of the tentacles monster?" I would say there are two different ways a story can be Lovecraftian. Firstly, the story can deal with a similar mythos - that is, tentacle monsters that smack strongly of Chthulu, like in your example - or the story can have a similar air to the writing (as I describe above, that is, Modernist tendencies and the horror being in the uncomprehensibility of the true universe).
Finally, you ask for a monster with tentacles that is not Lovecraftian. I nominate the giant squid from 20,000 Leagues Under the Sea (by Jules Verne) as definitively not Lovecraftian though it possesses an overabundance of tentacles.