Question on similar matrices and diagonalization. Let $A$ and $B$ be two $n\times n$ matrices with entries in a field $k$.

If $A$ and $B$ are similar, then can each one be obtained from the other via a combination of elementary row and column operations? Is the converse true?

I recall learning an equivalence relation on the set of $m \times n$ matrices with entries in $k$ that defined $Q$ and $P$ to be equivalent if they can be obtained from each other via combinations of elementary row and column operations, and I recall learning that this characterization is equivalent to saying there exists an invertible $m \times m$ matrix $U$ and an invertible $n\times n$ matrix $V$ such that $Q=UPV$. Is similarity the same relation restricted to the set of $n \times n$ matrices?
Any invertible matrix can be written as a product of elementary operations.  If you extend this arguement a bit, you'll see that, under the equivalence relation you've defined above, two matrices are equivalent if and only if they have the same rank.

If $A$ and $B$ are similar, then $A = M B M^{-1}$ for some invertible matrix $M$.  Thus, if two matrices are similar then they are equivalent under your relation.  

However, most matrices that have the same rank are not similar.  From the Rational Canonical Form for Matrices, we know that every matrix is similar to a block diagonal matrix (called the Rational Canonical Form) where the blocks are the companion matrices of certian polynomials called invariant factors of the matrix.  Two matrices are similar if and only if they have the same rational canonical form up to reorderings of the blocks.  Equivalently, two matrices are similar if and only if they have the same multiset of invariant factors.  Thus, by choosing the invariant factors appropriately, we can construct matrices that have the same rank but are not similar.

If the field has more than two elements, then a simpler argument is possible since similar matrices must have the same multiset of eigenvalues.  However, we can choose diagonal matrices that have different sets of eigenvalues but still have the same rank.  (This corresponds to the case where the invariant factors are linear polynomials.)  The advantage of the above argument is that it works even for $\Bbb{F}_2$.
Not always. Note that if you could find similar matrices by simple row/column interchanges, then you could easily diagonalize a symmetric real matrix, which means you can easily find its eigenvalues. But finding eigenvalues is a strictly iterative method and cannot be done in polynomial number of steps, because if you could find all eigenvalues, it would essentially mean you could completely determine the roots of a polynomial of degree $n$, but by Abel-Ruffini theorem, there exists no closed form expression for the roots of a polynomial of degree greater than $4$.

But suppose $A$ is a scalar matrix then any row interchange and subsequent column interchange will give you only $A$, so $A$ is similar only to itself.