2-local forms
As I have seen the term, 2-local Hamiltonians are those Hamiltonians $\hat H$ which can be written as a sum of independent qubit operators $\hat H = \sum_i \sum_j \hat O_{ij}$, where each $\hat O_{ij}$ acts non-trivially only on two qubits $i$ and $j$. This is as opposed to a global Hamiltonian, whose terms may act on any number of qubits.
This definition is related to the system being studied and does not make reference to implementation details such as qubit architecture. Operators $\hat O_{ij}$ may appear for any pair of qubits, not only adjacent pairs.
A little more elaboration
We can decompose any Hermitian operator on $n$ qubits into a weighted sum of Pauli "words": $\hat H = \sum_k c_k \hat P_k$ where each $\hat P_k$ is a tensor product of $n$ Pauli operators or the identity matrix: $\hat P_k\in\{I,X,Y,Z\}^{\otimes n}$. An arbitrary global Hamiltonian will decompose into as many as $4^n$ terms. If however we are guaranteed $k$-locality, there will only be ${n \choose k}\cdot4^k\in O(n^k)$ terms.
QAOA vs VQE
QAOA is indeed a special case of VQE, but the two algorithms use the term "Hamiltonian" a bit differently. In VQE, a quantum circuit is parameterized to prepare an "ansatz", and those parameters are varied classically to optimize a cost-function, which can be written as the expectation value of a so-called "Hamiltonian". That is, in general VQE, the Hamiltonian has nothing to do with the quantum circuit; it simply tells you how to measure the qubits to calculate the cost-function you are trying to optimize.
On the other hand, in QAOA, a completely different "Hamiltonian" is converted into its unitary time-evolution operator:
$$ \hat U \equiv e^{-i\hat H t} \approx \prod_{i,j} e^{-i \hat O_{ij}t}$$
This unitary operator is applied as the quantum circuit, and the classical variation is essentially varying the Hamiltonian itself. I am not personally familiar with the details of QAOA, and I am hoping that comments may elaborate upon the nature of that variation, and explain QAOA's cost-function.
Each $\hat U_{ij}=e^{-i\hat O_{ij}t}$ ostensibly needs to act on an adjacent pair of qubits, such that if $i$ and $j$ are not already adjacent, one needs a series of SWAPs to permute the qubits until they are. As I understand from the abstract, the paper you reference considers the problem of re-ordering a list of operators $\hat U_{ij}$ involving arbitrary (non-adjacent) pairs so as to minimize the number of swaps required on a specific qubit architecture.
2-local forms in VQE
I think the previous section answers your question about whether QAOA and VQE use the same Hamiltonian (in short, no!), but there are a couple other related concepts to briefly mention.
In principle, VQE can work with any Hamiltonian at all, local or global. That said, one can more strictly bound certain algorithmic complexity measures more tightly if the Hamiltonian is guaranteed to be $k$-local, since the number of independent measurements required to obtain the expectation value of $\hat H$ scales more-or-less with the number of terms in the Hamiltonian decomposition (technically with the number of commuting groups those terms can be partitioned into).
A typical application of VQE considers electronic structure of molecules. These Hamiltonians usually include only two-body interactions, although this is merely for the sake of approximation. So when you write out the Hamiltonian as a sum of operators on molecular orbitals, it looks like the 2-local form you wrote in your question. However, properly mapping the orbitals onto qubits (eg. via the Jordan-Wigner or Bravyi-Kitaev transformations) ends up breaking the 2-local form. The actual number of terms in the Hamiltonian is still polynomially bounded, but it becomes harder to efficiently partition the terms into commuting measurement groups.
