We may assume that $k_1+k_2 < L$, otherwise we simply could drop the constraint $\max(x_1,k_1)+\max(x_2,k_2)\geq L$ and solve the remaining system.
Now let $P=\{x\mid Ax\leq b, x\geq 0\}$. Further we define
$\begin{align*}
P_1&=P\cap\{x_1 \geq k_1, x_2 \geq k_2\},\\
P_2&=P\cap\{x_1 \geq k_1, x_2 \leq k_2\},\\
P_3&=P\cap\{x_1 \leq k_1, x_2 \geq k_2\},\\
P_4&=P\cap\{x_1 \leq k_1, x_2 \leq k_2\}.
\end{align*}$
We have $P=P_1\cup P_2\cup P_3\cup P_4$. Furthermore, it holds
if $x\in P_1$, then $\max(x_1,k_1)+\max(x_2,k_2) \geq L \Leftrightarrow x_1 + x_2 \geq L$;
if $x\in P_2$, then $\max(x_1,k_1)+\max(x_2,k_2) \geq L \Leftrightarrow x_1 + k_2 \geq L$;
if $x\in P_3$, then $\max(x_1,k_1)+\max(x_2,k_2) \geq L \Leftrightarrow k_1 + x_2 \geq L$;
if $x\in P_4$, then $\max(x_1,k_1)+\max(x_2,k_2) \geq L \Leftrightarrow$ false (since we assume $k_1+k_2<L$).
Now, let
$\begin{align*}
P_1'&=P_1\cap\{x_1+x_2\geq L\}\\
P_2'&=P_2\cap\{x_1+k_2\geq L\}\\
P_3'&=P_3\cap\{k_1+x_2\geq L\}\\
P_4'&=\emptyset\quad\mbox{(see above)}
\end{align*}$
and $P_1'\cup P_2'\cup P_3'$ is the set of feasible solutions of the originating system. Note although $P_1'$, $P_2'$ and $P_3'$ are convex, this set does not need to be convex.
Finally we minimize $c^Tx$ over each $P_i'$ individually. Taking the minimum of these values should be the solution of the originating problem.
Best Answer
Your problem is a second order cone programming (SOCP) problem. There are specialized interior point solvers for these kinds of problems that can be very efficient.