1) Let us replace the momentum indices ${\bf k}$ and $-{\bf k}$ with abstract indices $1$ and $2$, and ignore the momentum summation. The Hamiltonian then reads
$$\tag{1}H ~=~ \begin{pmatrix}a_1^{\dagger} & a_2\end{pmatrix}
M\begin{pmatrix}a_1 \\ a_2^{\dagger}\end{pmatrix},
$$
where
$$\tag{2} M~:=\begin{pmatrix}A & B\\B^{*} & A \end{pmatrix}~=~M^{\dagger},
\qquad A~\in~ \mathbb{R},\qquad B~\in~ \mathbb{C}.$$
A Bogoliubov transformation is on the form
$$\tag{3} \begin{pmatrix}a_1 \\ a_2^{\dagger}\end{pmatrix}
~=~U \begin{pmatrix}b_1 \\ b_2^\dagger\end{pmatrix}, \qquad U~:=~\begin{pmatrix}u_{11} & u_{12}\\u_{21} & u_{22}\end{pmatrix}.$$
Because a Bogoliubov transformation should preserve the canonical commutator relations (CCR), it is straightforward to check that the transformation matrix $U$ must belong to the Lie group
$$\tag{4} U(1,1)
~:=~\{U\in {\rm Mat}_{2\times 2}(\mathbb{C})
\mid U^{\dagger}\eta U~=~\eta \}, $$
where
$$\tag{5} \eta
~:=~\begin{pmatrix}1& 0\\0 & -1\end{pmatrix}$$
is the $1+1$ dimensional Minkowski metric. The Lie group $U(1,1)$ of Bogoliubov transformations is real and non-compact, and it is $4$-dimensional. In fact, one may prove that an element $U\in U(1,1)$ is of the form
$$\tag{6} U~=~\begin{pmatrix}u & v\\wv^* & wu^*\end{pmatrix},$$
where
$$\tag{7}u,v,w~\in~\mathbb{C},\quad |u|^2-|v|^2~=~1
\quad\text{and}\quad |w|~=~1. $$
The Hamiltonian then becomes of the form
$$\tag{8} H ~=~ \begin{pmatrix}b_1^{\dagger} & b_2\end{pmatrix}
N\begin{pmatrix}b_1 \\ b_2^{\dagger}\end{pmatrix},$$
where
$$\tag{9} N~:=~U^{\dagger}MU~=~N^{\dagger}.$$
Theorem I: We have the following two invariants under Bogoliubov transformations:
$$\tag{10} \det(N) ~=~\det(M)~=~A^2-|B|^2. $$
$$\tag{11} {\rm tr}(\eta N) ~=~{\rm tr}(\eta M)~=~0.$$
Proof of eq. (11): Use that $\eta N= U^{-1}\eta MU$ and $\eta M$ are connected via a similarity transformation. $\Box$
Corollary Ia:
The new $2\times 2$ matrix $N$ is of the form
$$\tag{12} N~:=\begin{pmatrix}A^{\prime} & B^{\prime}\\B^{\prime *} & A^{\prime} \end{pmatrix}~=~N^{\dagger},
\qquad A^{\prime}~\in~ \mathbb{R},\qquad B^{\prime}~\in~ \mathbb{C}.$$
It turns out that OP's assertion in the question formulation about diagonalizability is correct, cf. the following Corollary Ib.
Corollary Ib:
(i) The new $2\times 2$ matrix $N$ can only be diagonal if $|A|>|B|$ or $B=0$.
(ii) The new $2\times 2$ matrix $N$ can only be off-diagonal if $|A|<|B|$ or $A=0$.
(iii) If $|A|=|B|\neq 0$, then the new $2\times 2$ matrix $N$ is neither diagonal nor off-diagonal.
Proof of (i): The diagonal matrix $N$ must satisfy
$$ \tag{13} 0~\leq~ A^{\prime 2} ~=~ \det(N) ~=~\det(M)~=~A^2-|B|^2. $$
Hence $|A|>|B|$ or $|A|=|B|$. In the latter case, $A^{\prime}=0$, so $N=0$, and hence $M=0$, and in particular $B=0$. $\Box$
The proofs of (ii) and (iii) are left as exercises.
3) We will next argue that the case $A<|B|$ is not physically relevant, cf. Theorem II.
Theorem II:
(i) The Hamiltonian $H$ is positive definite if $A >|B|$.
(ii) The spectrum of $H$ is non-negative if $A\geq |B|$.
(iii) The spectrum of $H$ is unbounded from below if $A < |B|$.
A proof of Theorem II is left as an exercise. A proof at the classical level can be established by replacing the operators $a_1$ and $a_2$ with the corresponding classical complex variables, and then investigate the signature of the Hessian for the corresponding classical Hamiltonian function.
4) Finally, the Bogoliubov transformation (3) may be cast in a special relativistic language. One may view the matrix $M$, or equivalently $(A,B)$, as a point in $1+2$ dimensional Minkowski space with time coordinate $A\in \mathbb{R}$ and space coordinates $B\in \mathbb{C}\cong \mathbb{R}^2$. The invariant Minkowski length
$$\tag{14} \det(M)~=~A^2-|B|^2$$
is preserved under the action
$$\tag{15} \rho:U~\mapsto~ (U^{-1})^{\dagger}MU^{-1}$$
of the Lie group $U(1,1)$ of Bogoliubov transformations. Therefore $\rho$ is a Lie group homomorphism
$$\tag{16} \rho: \quad\to\quad O(1,2;\mathbb{R}) $$
into the $3$-dimensional Lorentz group $O(1,2;\mathbb{R})$. The condition $|A| >|B|$ ($|A| < |B|$) is the condition for being a time-like (space-like) vector, respectively. Intuitively, OP's observation concerning diagonalizability may be understood as the fact that one cannot turn a space-like vector into time-like vector by a Lorentz transformation.
Best Answer
There is always a bottom-line answer to this question: write the complex boson/fermion in terms of real boson/fermion ($a=a_R+i a_I$, etc), plug it in, and then diagonalize it by orthogonal matrices. This is probably the more natural way to do it for particle non-conserving systems.
If one insists on doing it in terms of complex boson/fermion, it's still possible, but many of the time annoying. This is because one (generically) also need to transform within the real and the imaginary part of the variables, which forces one to double the size of the matrix to include $( a,a^{\dagger},b,b^{\dagger})^T$ all together, like the Nambu spinor when one solves for superconductors' mean-field Hamiltonian. The annoying part is that one needs to take care of the redundancy in the matrix components.