Your teacher writes bad quiz questions, unless there were some very careful specifications added that would disqualify your answer and require the allegedly "correct" one. Teachers who write questions which they think have obviously correct answers have poor imaginations, penalise students with good imaginations and instil bad habits in the more impressionable students.
Both answers are good English; the meaning is almost identical. You could argue that construction out of paper implies that paper is the principal component, where construction with paper does not, but I cannot see how that is relevant.
Were there any extra rules or guidelines attached to the quiz? Did it specify single-word answers? If not, not only is your answer valid but a case might be argued for many others.
Bill can make a doghouse lined with paper. That's cool
Well, lining it with fur would be insanitary.
Bill can make a doghouse into paper. That's cool.
His dad built him a miniature wood-pulping machine in the back garden.
Oh, I dislike unimaginative teachers who abuse their god-like position to make such arbitrary and indefensible judgements.
Thinking about it some more, with doesn't even directly imply that the item specified is a component; with, in this case, is equivalent to using and it is up to the reader to infer, from context, whether the item is an ingredient or a tool.
Bill made a pyramid with cardboard, scissors and tape; his teacher had told him it would be good for sharpening razor blades.
Which is another distinction between with and out of but still doesn't justify your teacher's ruling.