Regular graphs are the graphs in which the degree of each vertex is the same. The Weisfeiler-Lehman algorithm fails to distinguish between the given two non-isomorphic regular graphs.
Is there a fastest known algorithm for regular graph isomorphism? Are regular graphs the hardest instance for graph isomorphism? Is there any combinatorial or algebraic technique (group theoretic) to deal with this situation efficiently?
The first place to look at is E.M. Luks algorithm for polynomial GI for graphs of bounded degree. The algorithm is group-theoretic, and utilizes the fact that subgroups of products of $S_k$ for bounded $k$ always have subgroups of bounded index, which allows to divide-and-conquer over cosets of an automorphism subgraph stabilizer efficiently (since for bounded degree graphs it is contained within products of $S_k$ induced by automorphisms of neighbourhoods of each vertex).
A recent breakthrough of Babai solves GI in $\mathrm{exp}(O((\log n)^c))$ time. One of the main ideas (which is not particuraly novel to this paper) is that either the (primitive) quotient of an automorphism subgraph stabilizer either has subgroups of small index (which allows to apply the previous result), or contains an automorphism group of a large Johnson scheme. The paper then proceeds to treat the second case with an efficient symmetry-breaking procedure, which is novel and highly non-trivial.
It would probably be an overly simplified and very imprecise statement, but this implies that the hardest case for GI are graphs obtained from a Johnson graph in a non-trivial way.
More about regular graphs (as asked in OP): all hard cases are regular of course, but some regular graphs are more susceptible than others. One usual method of solving GI is to promote several vertices by giving them unique colors, and doing WL-refinement or other tricks; if promoting a small set allows to refine the most of the graph, then this graph is easy for GI. The majority of regular graphs are easy with respect to this approach. The Johnson graph is hard in the following sense: to reduce the size of the largest equivalence class of vertices below $cn$ for $c < 1$, we may need to promote $\Omega(n^{c'})$ vertices, which prevents the trivial "try all sets" method to work within reasonable time.
One should distinguish between practical graph isomorphism and theoretical worst-case complexity. As Mikhail Tikhomirov mentioned, Babai's recent theoretical breakthrough gives the best asymptotic worst-case complexity, but his paper does not yield any breakthrough in practical graph isomorphism.
Practically, regular graphs are the hardest but for the rather uninteresting reason that if you have a pair of non-regular graphs then you can partition the vertices according to degree, and this generally breaks down the problem into easier sub-problems—the bottleneck is usually determining isomorphism of the "regular parts" and not figuring out whether they're pieced together isomorphically.
Variants of Brendan McKay's "nauty" algorithm are still the ones that are used in practice unless you know that you're dealing with a special class of graphs whose structure you can exploit. Perhaps surprisingly, it is not always the "most symmetric" graphs that are the hardest. One good reference is Tener's Ph.D. thesis. It is possible to construct hard instances for nauty, but some of these hard instances are relatively easily distinguishable by a special-purpose algorithm that actually requires a lot of symmetry. So, if we broaden the original question to ask if "highly symmetric" graphs are the hardest for the standard practical graph isomorphism algorithms, and if there are special algorithms that can handle these "hard cases," then there is a sense in which the answer is yes. However, this probably should be interpreted as saying that we still don't fully understand what the "hardest cases" of graph isomorphism are.
An algorithm which never distinguished between non-isomorphic regular graphs (of the same order) would be spectacularly weak. Some appropriate canonical form of the adjacency matrix is a (totally unusable) invariant which definitively determines isomorphism. Any invariant which sometimes fails to distinguish non-isomorphic graphs is likely to have some pairs $G,G'$ which are non-isomorphic, both regular, and not distinguished.
The article to which you link begins, in part:
The classical Weisfeiler-Lehman method WL[2] uses edge colors to produce a powerful graph invariant. ... Many traditionally used combinatorial invariants are determined by WL[k] for small k. We show that WL[2] determines the number of cycles of lengths up to 6.
So there are some cases of non-isomorphic graphs that WL[2] does not distinguish and certainly some of them are both regular. However such a pair would need to agree on the number of cycles of length $3,4,5,6$ and other things.
