Could something like, say, elephants losing their trunks or avian species losing/gaining the ability to fly happen in just a couple hundred thousand years or would it take millions?
The real truth is we don't know!
The theory of evolution continues to evolve itself, as we try to align it better and better with the evidence we have. One of the outstanding questions is how fast phenotypical changes like you describe occur. For a long time, the only standing theory was closely tied to what Darwin originally proposed, where changes occur slowly and gradually over many millions of years. However, it has been difficult to register this with the fossil records.
At the 10,000ft level, the smooth evolution picture looks very good. When you're looking at billions of years of evolution, you find a tree of life that has been growing smoothly. However, if we dig in, there are still questions to be answered. As we get closer and closer to what you and I would call the "birth" of a species, this smooth picture gets harder to sell. We generally don't see fossil records showing a smooth transition from one species to another. We see rapid jumps, where a new derived species suddenly arrives on the scene.
The scientific community does not have a consensus about how this should be dealt with. Many scientists, such as Richard Dawkins, posit that the issue is that our fossil record simply didn't capture the change because not every creature actually gets fossilized. However, some find this to be a strain. One solution proposed by Eldrege and Gould is Punctuated Equilibrium. In this model, the species stay relatively stable for long periods of time, interspersed with rapid changes that "create" a new species. In this model, the changes do indeed occur on the timeline you are interested in:
Although there exist some debate over how long the punctuations last, supporters of punctuated equilibrium generally place the figure between 50,000 and 100,000 years.
Now if you are looking at a prominent trait, one that defines the species for what it is, you may find that this occurs extremely rarely. It's very unusual for a species to lose something that is important to them because... well... it's important to them. The traits which we typically treat as prominent tend to be the ones that a species relies on for survival.
This has happened before. A key example is when animals moved onto land and shrugged off their primordial gills. However, it typically only occurs if a species is provided a great new opportunity where the value of diving into this opportunity head first outweighs the cost of losing something the species held dear. I would also conjecture that it does not occur often in times of great strife. In times of strife, it's much more energy efficient to find new ways to solve puzzles which add to your repertoire, rather than abandoning key survival features.
It is not time per se, but generation time which you have to consider. A human generation is approximately 20-25 years. A bacteria generation can be as little as 20 minutes. So if both those species took 100 generations to lose a trait, the bacteria would have done so in 2000 minutes (33 hours) but the humans will take 2000 years.
You also have to consider what trait they are losing. Flight is very useful to birds, but also very energy demanding. So in a situation where they don't need to fly - such as living on a remote oceanic island with no land predators - natural selection will favour flightless birds.
An elephant's trunk, on the other hand, is not merely useful, but vital. Without a trunk, an elephant cannot eat or drink. So evolution would first have to modify the elephant to provide an alternative way of reaching the ground to drink (giving it a long neck and kneeling/bending like a giraffe, say). So long as elephant species have that useful trunk performing perfectly well, there is no selection pressure to make an alternative to it.
I read a study a few years ago about the nerve density of human fingers. People born before 1990 tend -- TEND -- to have index finger as most sensitive, whereas those born later have thumb. This is the result of environmental shift, not gene mutation. But once environment pressure shifts for phenotype expression, that can cause genotype pressure. So the pressure driving a trait can ramp in the space of a generation. How long that takes to bring about change species-wide is an open research question.