Is the world Markovian according to modern theories (QM, GR, etc.)? Is the world Markovian according to modern theories (QM, GR, etc.)?
According to modern theories, is it true that there is no additional knowledge to be gained from the past for predicting the future if we know everything possible about the state of the universe in the present?
 A: Indeed, they are designed that way.  Physics is based on making predictions, and our best theories are designed to make their predictions assuming that you start with a state that has all the information you need to make your predictions.  Nothing else is assumed to be able to determine the future evolution, because if we thought it could influence it, then we'd include it as part of the current state.
But the state isn't a thing you can put in your pocket and pull it out to show your friends.  For instance, in general relativity you might need an initial value formulation, which wouldn't just include the metric at $t=0$, but also its derivatives (lapse and shift, etc.).  This is similar to Newtonian mechanics that requires at least the velocities as well as the positions of the parts.
In quantum mechanics it is worse, the state has a phase, but there is no known way to measure the phase, only relative phases (and those can still depend on gauge).  General Relativity has the same problem if you formulate it in terms of coordinates.  So in some sense the commonly used states are too much in that some states that look different are actually describing identical universes.  That's a problem we can live with, as long as we have enough states we can deal with having some parts that are ambiguous as long as the predictions are clear.
The other thing to keep in mind is that the basic equations of General Relativity are time-reversal invariant, you predict the past as well as you predict the future (so a singularity in the past or the future creates a problem, as would a time machine).
So I basically already said yes, but let's look for hidden assumptions and bias. You talked about "if we know everything possible about the state of the universe", and that leads to an important distinction, the difference between the state of the universe (that which I described above) and our state of knowledge of the universe (a different issue).  People do still argue about which states we should be modelling or which we are modelling.  But I haven't seen someone argue that the past (as opposed to the present) is a useful way to supplement our knowledge.
Because in the absence of time machine we don't have direct access to the past, we can only indirectly access the past based on how it has influenced the present.  In your linked example of a nonmarkovian process, the information about the past is right there in your hand in the present and you just ignore it.  In physics if the information about the past was not accessible it makes an actual testable prediction about what we see.  
For instance in the classical a double slit experiment, if the particle interacted with the environment in such as way as to leave a record of it's past being in one of those slits, then the interference pattern is destroyed.  Only when no record survives (even in principle, not just because we are lazy or indifferent) is there interference, and then the question of where it was in the past becomes a subject of academic debate because there is no evidence, and there is evidence of the permanent forever more lack of evidence (people can tell stories and make theories, but there is no evidence outside of a particular theoretical vantage point).
So modern physics actually goes so far as to say there is evidence that there is no past beyond the present.
