I attacked with a 4/4 creature. The opponent blocked with a 1/1. Before combat damage was assigned, they cast Smite the Deathless on my 4/4, dealing it 3 damage, and causing it to lose indestructible until end of turn. If I then cast Orcish Medicine (which can give indestructible until end of turn) on the 4/4 before combat damage is assigned, can it gain indestructible?
113.10c If two or more effects add and remove the same ability, in general the most recent one prevails. See rule 613 for more information about the interaction of continuous effects.
Basically, to summarize at a high level what 613 says, an object’s abilities and other attributes will be determined by starting with what’s printed on the card; and then applying each effect that changes that one at a time. Removing indestructible and adding indestructible both happen in the same layer, so they are applied in timestamp order.
Because Orcish Medicine happened after Smite the Deathless, its effect will be applied after and wins.
Gendolkari's correct answer summarizes how two opposite effects interact (most recent one wins).
I'll just point out an alternative line of play that your opponent could have taken that has a different outcome. If they had waited until after combat damage occurred to cast Smite the Deathless, you would have no way to save your creature with your Orcish Medicine. Because you can't interrupt the individual steps of a spell or ability, there is no window of opportunity for you to reapply indestructible because your creature would have already died (and gone to exile) from the 3 damage.
Likewise, the timestamp system in Gendolkari's answer means that applying indestructible before the Smite is also useless because the Smite would remove the redundant indestructible and still kill the target.