Finding odd holes in circulant Paley graphs
I believe there is a known poly(q) algorithm. My understanding of the algorithm by Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković, "Recognizing Berge Graphs", Combinatorica 2005, is that it finds either an odd hole or an odd antihole in any non-perfect graph in polynomial time. The authors write on page 2 of their paper that the problem of finding odd holes in graphs that have them remains open, because steps 1 and 3 of their algorithm find holes but step 2 might find an antihole instead. However, in the case of Paley graphs, if you find an antihole, just multiply all the vertices in it by a nonresidue to turn it into an odd hole instead.

Alternatively, by analogy to the Rado graph, for each k there should be an N such that Paley graphs on N or more vertices should have the extension property: for any subset of fewer than k vertices, and any 2-coloring of the subset, there exists another vertex adjacent to every vertex in one color class and nonadjacent to every vertex in the other color class. If so, then for k=5 you could build an odd 5-hole greedily in polynomial time per step. Maybe this direction is hopeful for a poly(log(q)) algorithm? If it works it would at least show that there are short odd holes, seemingly a necessary prerequisite to finding them quickly.

Actually, it wouldn't surprise me if the following were a poly(log(q)) algorithm: if q is smaller than some fixed constant, look up the answer, else greedily build an odd 5-hole by searching sequentially through the numbers 0, 1, 2, 3, ... for vertices that can be added as part of a partial 5-hole. But maybe proving that it works in poly(log(q)) time would require some deep number theory.

By results of Chung, Graham, and Wilson, "Quasi-random graphs", Combinatorica 1989, the following randomized algorithm solves the problem in a constant expected number of trials when q is prime: if q is sufficiently small then look up the answer, else repeatedly choose a random set of five vertices, check whether they form an odd hole, and if so return it. But they don't say whether it works when q is not a prime but a prime power, so maybe you'd need to be more careful in that case.