We can show this without having to deal with integrals, or the normal density function. It arises from a symmetry property, and the normal density of $x$ decreasing as $|x|$ increases.
First, note that this is trivial for $k \leq 0$, since then $\mathbb{P}(|X| > k) = 1$ for all $\mu$. We therefore only need to examine the case where $k > 0$.
Let $$f(\mu; k) := \mathbb{P}(|X| > k \,;\, \mu) = 1 - \Phi\left(\frac{k-\mu}{\sigma}\right) + \Phi\left(\frac{-k-\mu}{\sigma}\right).$$
This is symmetric in $\mu$, since $\Phi(x) = 1 - \Phi(-x)$:
$$f(-\mu; k) = 1 - \Phi\left(\frac{k+\mu}{\sigma}\right) + \Phi\left(\frac{-k+\mu}{\sigma}\right) = 1 + \Phi\left(\frac{-k-\mu}{\sigma}\right) - \Phi\left(\frac{k-\mu}{\sigma}\right) = f(\mu;k).$$
We can therefore restrict ourselves to considering positive values of $\mu$.
We now differentiate by $\mu$:
$$f'(\mu;k) = \frac{\textrm{d}}{\textrm{d}\mu} \mathbb{P}(|X| > k \,;\, \mu) = \phi\left(\frac{k-\mu}{\sigma}\right) - \phi\left(\frac{-k-\mu}{\sigma}\right),$$
where $\phi$ is the normal density function. For the proposed property to hold, we require $f'$ to be positive for all $\mu \geq 0$, which is equivalent to
$$\phi\left(\frac{k+\mu}{\sigma}\right) \leq \phi\left(\frac{k-\mu}{\sigma}\right) \quad \textrm{for all } \mu \geq 0.$$
This is true if and only if $|k+\mu| \geq |k-\mu|$, since $\phi(x)$ decreases as $|x|$ increases. $k + \mu > 0$, since $k > 0$ and $\mu \geq 0$, so we have two cases:
- $k \geq \mu$, and we require $k+\mu \geq k-\mu$, i.e. $\mu \geq 0$, which is true.
- $k < \mu$, and we require $k+\mu \geq \mu-k$, i.e. $k \geq 0$, which is true.
Therefore, the property is true for all $k$.
Some examples using R:
f <- function(mu, k) 1 - pmax(0, pnorm(k, mu, 1) - pnorm(-k, mu, 1))
curve(f(x, 0), from = -5, to = 5)
curve(f(x, 1), from = -5, to = 5)
curve(f(x, 10), from = -5, to = 5)
This also holds for any other density function that's "symmetric-decreasing". Here are some examples for the Cauchy distribution:
f <- function(mu, k) 1 - pmax(0, pcauchy(k, mu, 1) - pcauchy(-k, mu, 1))
curve(f(x, 0), from = -5, to = 5)
curve(f(x, 1), from = -5, to = 5)
curve(f(x, 10), from = -5, to = 5)