Yes, a tiefling's horns and tail could be removed
No material specifies that they cannot, nor any mechanical effects or penalties for a tiefling that is mutilated in such a fashion. The nearest we get is that the DMG, on page 272, includes an optional rule about lingering injuries which has examples including severed limbs. For instance, losing an arm:
Lose an Arm or a Hand. You can no longer hold anything with two hands, and you can hold only a single object at a time. Magic such as the regenerate spell can restore the lost appendage.
So losing a body part does not inherently incur permanent HP loss. However, another example is the "festering wound", which does reduce your HP maximum over time until the wound is healed magically or otherwise, so a tiefling that is mutilated might suffer such damage due to a lack of appropriate medical care:
Festering Wound. Your hit point maximum is reduced by 1 every 24 hours the wound persists. If your hit point maximum drops to 0, you die. The wound heals if you receive magical healing. Alternatively, someone can tend to the wound and make a DC 15 Wisdom (Medicine) check once every 24 hours. After ten successes, the wound heals.
For a significant injury to the head/face such as that incurred by removing the horns, the "horrible scar" injury might be appropriate:
Horrible Scar. You are disfigured to the extent that the wound can't be easily concealed . You have disadvantage on Charisma (Persuasion) checks
and advantage on Charisma (Intimidation) checks. Magical healing of 6th level or higher, such as heal and regenerate, removes the scar.
I would also be inclined to say that a tiefling that is suddenly missing their tail should be at disadvantage on acrobatics and athletics checks for a while at least, since for any creature with a tail that large it will significantly affect their balance, but could get used to it with some time.
In any event, whether or not permanent hit point loss is incurred, the removal of the appendages would be a significant physical trauma that should definitely cause hit point damage at the time, which would need to be healed like any other.
No, they won't grow back without magical assistance
In nature, damaged horns may or may not regrow based on the extent of damage done to them and the type of horn. True horns, such as those possessed by goats and cattle, are live bone with a keratin exterior, and have a blood supply and such. They are not like antlers (which are dead bone, shed and regrown every year) or other horn-like growths (such as that of the rhinoceros, which are pure keratin and will regrow if severed, like a fingernail).
The depictions of tiefling horns in official artwork seem most like true horns in the style of bovine animals. Chips to the exterior of a true horn will probably regrow and limited damage to the bony core could heal, but if snapped or completely removed they won't just grow back on their own (though a snapped horn can be set like a broken bone and may heal back together).
A severed tail is unlikely to regrow much if at all - most creatures that lose tails might regrow a very short stump at best.
In both cases being subject to the Regeneration spell would immediately cause lost appendages to start regrowing:
The target's severed body members (fingers, legs, tails, and so on), if any, are restored after 2 minutes.
As per this question, a character probably cannot pick-and-choose which body parts they would regenerate if affected by the spell, so the regeneration of horns and tail would occur even if the subject found that an undesirable effect.
In the general case, assume that people heal like they do in real life unless otherwise stated. If you pull out a person's teeth they don't grow back, nor if you cut off parts of their ears.