Your teacher is wrong. Firstly, note that the presence or absence of a problem has nothing whatsoever to do with the MWI - what is being described could happen in this universe, without recourse to the MWI, it would just be astronomically improbable. However, if this series of events were truly a paradox, it would have to be strictly impossible, and so the problem would be present or absent whether the series of events is astronomically improbable as is the case without MWI or whether it the series of events is virtually certain to occur as is the case when we consider all possible worlds in the multiverse in MWI. Thus, we can entirely disentangle the MWI from this question.
Now, the resolution of the apparent paradox is hinted at in the question you ask in point 2). An information paradox occurs if we can reliably communicate information back in time. By assumption, the series of events we describe doesn't constitute that - it occurs purely by random chance.
To see this more clearly, suppose instead that in the year 2000 I walked into a door (could be a door to a funky contraption that looks like a time machine, or it could just be a regular door to a library) carrying the complete works of Shakespeare (I don't even dematerialise as I walk through, I continue and exit on the other side just fine), and in the year 1999 I walked out of a door carrying the complete works of Shakespeare (once again I had walked in normally, no magic materialisation happening here either). Has an information paradox occurred in this scenario? Have I transmitted the works of Shakespeare back in time?
"Of course not," you say, "but the situations are fundamentally different - the alleged time-traveller I described dematerialised in the future, and materialised in the past." But, so what? The dematerialisation/materialisation events are far more improbable than the walking in/walking out of a door events, but they are not fundamentally any different - both are due to random fluctuations and in both cases the works of Shakespeare were present at a future time and present at a past time, one is just far more likely to occur than the other. But clearly, in the second case we would not suggest that any information has been transmitted back in time.
The apparent contradiction stems from our thinking that just because certain random fluctuations are possible in our universe they are properly "caused" by the laws of our universe. That is not to say that events in a universe with probabilistic laws are totally randomly caused - we have compelling evidence that they follow particular, albeit probabilistic, laws. Rather, you can think of a series events having two causal elements - reliable, definite, physical laws, which determine a probability distribution of series of possible events, and then a random element that selects from this distribution.
For information to be transmitted reliably from event A to event B, event A must through the physical laws affect the probability distribution element of B's cause in a way that makes it highly likely for that information to emerge at event B. This is clearly not what is happening in either case above.
Event A - which in the first case is the dematerialisation of the alleged time-traveller in the future with the complete works of Shakespeare, and in the second case is me walking in to a door with the complete works of Shakespeare - has, as per the physical laws of our universe (relativity, quantum mechanics, etc.), no bearing whatsoever on the probability distribution element of the cause of event B - which in the first case is the materialisation of the alleged time-traveller in the past with the complete works of Shakespeare, and in the second case is me walking out of a door with the complete works of Shakespeare.
These just happen for unrelated reasons - in the first case, sheer random chance causes the highly improbable materialisation event to occur, and in the second case some unrelated set of causes (having to do with me being a perennial bookworm) lying strictly in the past of event B shape the probability distribution, making it likely for me to walk out of the door with the complete works of Shakespeare. In either case, no information is transferred from event A to event B, and there is no information paradox.