Consider a Wang tiling (given a subset of $C^4$ for a finite set $C$ of colours, e.g.). It's well-known to be undecidable whether there exists a tiling, and also whether there exists a periodic tiling. It's also well-known that there exists a periodic tiling iff there exists a doubly periodic tiling.

On the other hand, for any given n, then it's decidable whether there exists a periodic tiling with period $(n,0)$: construct a directed graph with vertex set $C^n$ and an edge from $v$ to $w$ if there exists a tiling of the $n\times1$ rectangle with identical left and right labels and $v,w$ at the bottom and top respectively. Then there exists such a periodic tiling iff this graph has a loop.

Here is a question I can't answer: for any given $n$, is it decidable whether there exists a periodic tiling with period $(n,m)$ for some $m$?