This is not an answer, but too long for a comment. 

***

Consider a *doubly infinite* matrix $L = (q_{ij})_{i,j \in \mathbb{Z}}$ with entries $q_{ij} = -e^{-|i - j|}$ when $i \ne j$, and $q_{ii} = 2 e / (1 - e)$; here $i, j \in \mathbb{Z}$. The symbol of this matrix (i.e. the Fourier series with coefficients $e^{-|j|}$, except at $j = 0$) is:
$$ \psi(x) = \frac{e^2 - 1}{e^2 - 2 e \cos x + 1} - \frac{e + 1}{e - 1} . $$
The symbol of $L^\dagger$ is thus $1 / \psi(x)$ (in the principal value sense), which has a singularity of type $1 / x^2$ at $x = 0$. It follows that in this case
$$ a_{kl} = \frac{1}{2 \pi} \int_{-\pi}^{\pi} \frac{(e^{i x} - e^{2 i x}) (e^{i k x} - e^{i l x})}{\psi(x)} \, dx . $$

In general, the above expression will only have *power-type* decay as $k,l \to \infty$.

However, for this particular choice of $L$, things simplify a lot. The pseudo-inverse $L^\dagger = (u_{ij})_{i,j \in \mathbb{Z}}$ can be found explicitly, and its entries are $u_{ij} = C_1 - C_2 |i - j|$ when $i \ne j$ and $u_{ii} = C_3$ for appropriate constants $C_1$, $C_2$, $C_3$. Consequently, $a_{kl} = 0$ when $k, l > 2$.

***

I do not have a clear intuition about what happens in the one-sided case (that is, if we consider an infinite matrix $L$ with entries indexed by $i, j \in \{1, 2, \ldots\}$), let alone the bounded case (with $i, j \in \{1, 2, \ldots, n\}$). My wild guess would be that the symmetry breaks, and there is no hope for any closed-form formula.

However, a quick numerical experiment suggests strongly that we still have $a_{kl} = 0$! More precisely, the entries $u_{ij}$ of $L^\dagger$ apparently satisfy
$$
 u_{ij} = v_{\max\{i,j\}} + v_{\max\{n+1-i,n+1-j\}}, v_{n-i} + v_j\} + \tfrac{1}{4} |i - j| \qquad (i \ne j)
$$
for an appropriate vector $v_i$. I find this *extremely* surprising!

Here is the code in Octave, in case anyone is interested. First, we construct $L$ and its pseudo-inverse (denoted `U` here):
```
n = 10;                                  # size of the matrix
A = toeplitz(exp(-(0:n-1)));
L = diag(A * ones(n,1)) - A;             # matrix L
U = pinv(L);                             # pseudo-inverse L^\dagger
```
Next, we verify that the mixed second-order difference of $L^\dagger$ is a tri-diagonal matrix:
```
D = U(1:n-1, 1:n-1) - U(1:n-1, 2:n) ...
    - U(2:n, 1:n-1) + U(2:n, 2:n);       # second-order difference of U
```
This already shows that $L^\dagger$ has the desired structure, but we can verify this directly. First two lines are to extract the vector $v_i$, the other two define the matrix `Z` with entries
$$
 u_{ij} - v_{\max\{i,j\}} - v_{\max\{n+1-i,n+1-j\}}, v_{n-i} + v_j\} - \tfrac{1}{4} |i - j| \qquad (i \ne j)
$$
which should be zero except on the diagonal:
```
X = U - 0.25 * abs(repmat(1:n, n, 1) - repmat(1:n, n, 1)');
V = X(:, 1) - 0.5 * X(n, 1);
I = repmat(1:n,n,1);
Z = X - V(max(I, I')) - V(max(n + 1 - I, n + 1 - I'));
```