We show that $m = 7^{n-1}$ works. By the lifting the exponent lemma, we have
$$v_7(3^m + 4^m) = v_7(3^m + 4^m) + v_7(m) = 1 + (n-1) = n.$$
This implies $7^m \mid 3^m + 4^m$, and hence $3^m \equiv -4^m \pmod{7^n}$. Similarly, $5^m \equiv -2^m \pmod{7^n}$. It follows that
$$3^m + 5^m - 1 \equiv -4^m - 2^m - 1 \equiv -(2^{2m} + 2^m + 1) \pmod{7^n}. \quad (1)$$
Next, again by the lifting the exponent lemma, we have
$$v_7(8^m - 1) = v_7(8^m - 1) + v_7(m) = 1 + (n-1) = n.$$
This implies $7^m \mid 8^m - 1 = (2^m - 1)(2^{2m} + 2^m + 1)$. As $3 \nmid m$, we have $7 \nmid 2^m - 1$. Therefore, we must have
$$7^m \mid 2^{2m} + 2^m + 1. \quad (2)$$
Combining (1) and (2), we see that $7^m \mid 3^m + 5^m - 1$ as desired.