Let $K$ be a field s.t. $charac(K)\not= 2$. Let $A\in\mathcal{M}_n(K)$ be such that $rank(A)\geq n/2$. Can one find a matrix $B$ such that $B$ is similar to $A$ and $A+B$ is invertible ?

Initially my assumption was that the question was primarily about finite fields $K$, but after reading the comments it appears to me that there is some confusion about the infinite case as well. So I'll prove the claim for $K=\infty$. I would guess the assertion is also true if $K$ is finite, but I don't know how to show it. If one assumes $K$ to be algebraically closed, then it's very easy to see that one can find an appropriate $B$: Let $\lambda_1,\ldots,\lambda_n$ be the eigenvalues of $A$ (eigenvalues with multiplicity $m$ are supposed to appear $m$ times in that list), then for any permutation $\sigma\in S_n$ we can conjugate $A$ to a matrix of the form $$ \textrm{diag}(\lambda_{\sigma(1)}, \ldots, \lambda_{\sigma(n)}) + N $$ where $N$ is a strictly upper triangular matrix. (This should be clear but I'll give a short explantion anyhow: View $K^n$ as a $K[x]$ module where $x$ acts as $A$. Then finding a basis that conjugates $A$ into the form given above corresponds to finding a filtration $0= V_0 < V_1 <\ldots< V_n= K^n$ of the $K[x]$module $K^n$ such that the quotient $V_i/V_{i1}$ is isomorphic to the simple $K[x]$module $K[x]/(x\lambda_{\sigma(i)})$. But by the structure theorem on f. g. modules over PID's, $K^n$ is a direct sum of modules each having just one isomorphism type of simple modules as composition factors. So choosing such a filtration is no problem: in each step just pick a maximal submodule in the desired isotypic direct summand and leave the other summands unchanged.) We may assume that $A$ is of the above shape with $\sigma=\textrm{id}$. So just choose a permutation $\sigma$ such that $\lambda_i+\lambda_{\sigma(i)} \neq 0$ for all $i$ (this can be done: just choose $\sigma$ to be the transposition that swaps each $\lambda_i$ which is zero with some $\lambda_i$ which is nonzero and fixes the rest; the rank condition implies that there are enough nonzero eigenvalues to pair with the zero eigenvalues; also $char(K)\neq 2$ is essential: it guarantees $\lambda_i\+\lambda_i\neq 0$ whenever $\lambda_i\neq 0$). Then $A+B$ can becomes $$ \textrm{diag}(\lambda_1+\lambda_{\sigma(1)}, \ldots, \lambda_n+\lambda_{\sigma(n)}) + \textrm{something strictly upper triangular} $$ and you are done. As for the case of a nonalgebraically closed (but still infinite) $K$: Note that the algebraically closed case implies that the rational function $$ det(A+TAT^{1})=\frac{det(AT+TA)}{det(T)} \in K(T_{ij}) $$ is nonzero. But $GL(n,K)$ is Zariski dense in $GL(n,\bar K)$ (see here), and so the above rational funktion must be nonvanishing on $GL(n,K)$, which shows there is a $T\in GL(n,K)$ such that $det(A+TAT^{1})\neq 0$. 

