It’s not only believable that they could safely eat things humans could not, it’s almost expected.
Put simply, toxicity is a function of biochemistry and dose.
Consider for a moment why penicillin is useful as a medication. It’s lethally toxic to many bacteria in doses that are not generally enough to have any measurable impact on mammalian cells (even most of the side effects are actually a result of it disrupting a person’s natural gut bacteria). Many (but not all) other antibiotics are relatively similar. This arises from the fact that bacterial biochemistries are different enough from human biochemistry that there is limited overlap in toxicity of many toxins.
In contrast though, many antifungal and antiprotozoal medications (for example, amphotericin B or quinine) are actually mildly toxic to humans, and require much more careful dosing as a result, because fungi and protozoans have much closer biochemistries to those of humans.
Even some ‘regular’ medications that aren’t trying to kill specific things have relatively narrow gaps between being safe and medically useful and being lethally toxic. Digoxin, atropine, and warfarin are all prime examples of this (all three are considered essential medications by the WHO, all three are also nastily toxic if you have even just a bit too much).
You can find a number of other examples as well:
- Most felid and canid species cannot safely eat many species of Allium, though humans use Allium species regularly as food (onions, leeks, shallots) or seasonings (garlic, chives) with essentially no ill effects.
- Chili peppers are ‘spicy hot’ to pretty much all mammals, but not to most birds.
- Atropa belladonna (commonly known as deadly nightshade) is nastily toxic to humans and most other mammals, but a number of bovid and leporid species have no observable issues eating it.
- Horseradish is perfectly safe for humans to eat, but potentially lethally toxic to horses (which is, ironically, where it’s name comes from).
Veterinarians can probably easily list dozens of other examples of things that are toxic to certain animals, but not humans.
But it inherently won’t work for everything.
Barring drastically different biochemistries, some things will still be toxic to both this species and to humans.
For example, most metals and other ‘pure’ elements are toxic regardless of species because of limitations in terrestrial biochemistry. In particular, most cells cannot differentiate very well between different ions with the same ionization state.
Arsenic poisoning is a prime example of this. Arsenic ends up as arsenate ions in the body, which look to your cells like they’re no different from phosphate ions. As a result, those arsenate ions end up getting substituted for phosphate ions when the cells are producing adenosine triphosphate (ATP). But the arsenate groups don’t bind anywhere near as strongly as the phosphate groups do, so the adenosine diphosphate arsenate that gets produced in place of ATP just kind of falls apart, wasting the energy that it was supposed to be storing.
This ultimately means that pretty much anything that uses ATP and produces it in a similar way to humans is affected by arsenic poisoning.
You can find similar (and usually even more broad spectrum) cases for most other elements known to be toxic. A lot of these are still likely to be toxic to your aliens given that they have a close enough biochemistry that they can share food with humans.