Complexity of Linear Diophantine equations
Yes, this class of equations can be solved in polynomial time.  In particular, there exists a solution if and only $\gcd(a_1,\dots,a_n)$ divides $k$.  That condition can be tested in polynomial time, since there are polynomial-time algorithms to compute the gcd.  In addition, if a solution exists, one can be found using the extended Euclidean algorithm.