Bamboo is a grass and doesn't come from a tree. Palm wood comes from palm trees, except palm tree trunks are apparently a totally different type of structure than other tree trunks, sounds closer to Papyrus. No growth rings, a fiber type structure. Is Papyrus wood?
Any plant matter above a certain density? I don't think that's it. Corn stalks aren't wood.
Man, I don't know. I am certain that it must be plant matter though, so yes, a wooden frog would be a biological miracle.
My total armchair answer: It helps to think about trees as just giant shrubs.
Shrubs are considered "woody", but most definitely are not trees. There are plenty of trees which are close relatives of shrubs (like poison oak and the urushi tree).
So what's the difference between a grass and a tree? Walking the tree of life up from Poison Oak and Bamboo, we see we land at Monocotyledon and Eudicots. There's lots of non-woody and tough fibrous (i.e. woody) plans in both clades (palm trees are monocots, btw).
Wikipedia says if it is tough and fibrous and has growth rings it's wood:
https://en.wikipedia.org/wiki/Wood
So Bamboo, although coming from a grass and not a tree, is wood. Further reading down that page talks about density as a key quality of wood, and goes on to not definitively quality bamboo as wood or as non-wood but some are dense enough.
Ultimately, there's no super clean definition of wood is my take-away, between the technical and colloquial aspects. You can use bamboo in construction much like wood, if you cut off a bit of shrub and dry it out, it's a "stick" just as much as if you trimmed it off a tree. You can make paper out of all kinds of fibers.