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.
Hint:
The problem is equilvalent to:
$$\min_x \sum_{i=1}^n \max(x_i, -x_i)+\max(x_1, \ldots, x_n)$$
subject to
$$Ax=b$$
How would you rewrite sum of minimax as a linear programming problem.
Remark: $Ax=b$ doesn't affect the main problem of interest. Just copy it down as it is.
Edit:
$$\min \sum_{i=1}^n z_i + t$$
subject to
$$z_i \ge x_i , \forall i \in \{1, \ldots, n\}$$
$$z_i \ge -x_i , \forall i \in \{1, \ldots, n\}$$
$$t \ge x_i , \forall i \in \{1, \ldots, n\}$$
$$t \ge -x_i , \forall i \in \{1, \ldots, n\}$$
$$Ax=b$$
You can also write them in terms of vector form as you have shown in the comment as well.
Best Answer
This can be easily achieved by adding one dummy variable. \begin{align} \min_P \quad &(\max (K_1+P,0)+ K_2 P)\\ P &\in \mathcal{P}\\& \Updownarrow\\ \min_P\quad &t+K_2P\\P&\in \mathcal{P}\\t&\geq K_1+P\\t&\geq0 \end{align}