Is the complexity of this path problem known?
Assume there are no self-edges in $G$.

For each edge between node $v_i$ and $v_j$ in $G$, let $E[i,j]=1$, and $E[i,j]=0$ if there is no edge. Compute $n\times n$ matrix $C[i,j]=\sum_{k=1}^n E[i,k]\cdot E[k,j]$, which gives the number of two-hop paths between each pair of nodes $v_i$ and $v_j$. Then for edge between $v_i$ and $v_j$ in $G$ compute $D[i,j]=E[i,j]\cdot C[i,j]$ otherwise set $D[i,j]=\infty$, which gives the number of triangles the edge is part of (or infinity if there is no edge). The matrix multiplication needed to compute $C$ costs $O(n^3)$ (could be computed faster depending on sparsity of $G$). 

Now compute $n\times n$ matrix $A$, such that $A[i,j]=\min(D[i,j],\min_k(D[i,k]+D[k,j]-E[i,j]))$. $A$ is all shortest-paths in $D$ of length up to two augmented to account for paths that go along two edges of some triangle. 

Now just compute the shortest path between $v_i$ and $v_j$ in $G$ on a new graph of which $A$ is the (weighted) adjacency matrix using Dijkstra (since all edge-weights are positive) i.e. and determine if $A^*[i,j]\leq k$, where $A^*$ is the closure over the tropical semiring (which gives the distance matrix).