Generally how much proof must be given to prove a statement of order-of-magnitude? for example:
$n^2 + 2 \log (n) = O(n^2)$
$2 \log (n)$ has a lower order of magnitude than $n^2$ so it can be argued that $n^2 = O(n^2)$. Is this enough proof?
The statement $5^n = O(n!)$ is another, is simply listing a few numbers of $n$ enough proof to show that $5^n$ is not a higher order-of-magnitude?
Just keep it simple. Follow the definition. Just show that there is a positive constant $K$ such that $ n^2 + 2 \ln n \le K n^2 $ for sufficiently large $n$. Definitely listing a few elements will not constitute a proof.
All you really need to know is the inequality that $ n \ge \ln n $ which can be established by observing the behaviour of the function $ x - \ln x $.
Then $$ n^2 + 2 \ln n \le n^2 + 2 n \le n^2 + 2n^2 = 3 \cdot n^2 \; \forall n \in \Bbb N $$
As for the second question, listing a few numbers might not give you the claimed result unless you are clever to pick the right positive constant.
Hint: $ 5^5 = 3125. $