National Math Olympiad

The answer is yes. If one of the digits is even, then Matej can form two even numbers by putting the piece of paper with the even digit in the place of units and exchanging two of the other three pieces of paper. If one of the four digits is equal to $5$, then Matej can act similarly. He should put the piece of paper with the digit $5$ in the place of units and again exchange two of the other three pieces of paper. The resulting two numbers are not relatively prime since they are both divisible by $5$. If two of the digits are the same, then Matej can make an arbitrary number and then simply exchange the two pieces with the same digits to get the same number.

The only remaining case is where the digits are $1$, $3$, $7$ and $9$. With these, Matej can form either the numbers $1397$ and $1793$ or the numbers $1397$ and $9317$ or the numbers $9317$ and $9713$. All of these are divisible by $11$. He can also form the numbers $1739$ and $9731$, which are both divisible by $37$.