Let $A^k_{i,j} = (n^k_{i,j}, s^k_{i,j})$ where $n^k_{i,j}$ is the number of paths of length $k$ between $i$ and $j$, and $s^k_{i,j}$ is the sum of the lengths between these paths.
$A^1_{i,j} = (1, w_{i,j})$ if $ij$ is an edge, else $A^1_{i,j}=(0,0)$
The idea of the recurrence is that a $(k+k')$-step path from $i$ to $j$ is composed of a $k$-step path from $i$ to an intermediate vertex $c$ followed by a $k'$-step path from $c$ to $j$.
Let fix $c$. Let $n_1$ (resp $n_2$) be the number of $k$-step paths from $i$ to $c$ (resp. $k'$-step paths from $c$ to $j$) and $s_1$ (resp. $s_2$) the sum of weigths on these paths.
We can easily see that the number of $(k+k')$-step paths from $i$ to $j$ passing through $c$ at step $k$ is $n_1n_2$. The sum of weights is $s_1n_2 + s_2n_1$ because each path from $i$ to $c$ will appear in exactly $n_2$ paths, and conversely. To get the total number of $(k+k')$-step paths from $i$ to $j$, we just need to sum over the $c$. So the recurrence is given by :
$$A^{k+k'}_{i,j} = (n^{k+k'}_{i,j}, s^{k+k'}_{i,j}) = \sum_{c\in V}(n^k_{i,c}n^{k'}_{c,j}, n^k_{i,c}s^{k'}_{c,j}+s^k_{i,c}n^{k'}_{c,j})$$
We can adapt the definition of the matrix multiplication by replacing the multiplication by :
$(n_1,s_1)\otimes(n_2,s_2) = (n_1n_2, n_1s_2 + n_2s_1)$
and addition by :
$(n_1,s_1)\oplus(n_2,s_2) = (n_1+n_2, s_1+s_2)$
With it, we have :
$$A^{k+k'}_{i,j} = \bigoplus_{c\in V} A^{k}_{i,c}\otimes A^{k'}_{c,j}$$
and so $A^kA^{k'} = A^{k+k'}$
The new matrix multiplication is associative, so matrix exponentiation by squaring still work.
This kind of redefinition of the matrix multiplication is common when dealing with shortest paths, see the min-plus matrix multiplication
Best Answer
maybe this paper, in which the calculation of the all pairs shortest paths in $O(n^2)$ with high probability is solved, meets your requirements.
Some preconditions about the distribution of edge lengths are made, which you could check against the properties of your problem instances.