A (total) dominating set \( D \) of a graph \( G \) with no isolated vertices is called a paired dominating set, if the subgraph induced by \( D \) in \( G \) contains a perfect matching. The decision problem Paired Domination takes as input a graph \( G \) and a positive integer \( k \) , and asks whether \( G \) contains a paired dominating set of size at most \( k \) . Paired Domination is known to be NP-complete for planar bipartite subcubic graphs. In this paper, we prove that Paired Domination remains NP-complete on planar cubic graphs and, assuming the Exponential Time Hypothesis (ETH), the problem cannot be solved in time \( 2^{o(\sqrt{|V(G)|})} \) in planar cubic graphs. We also show that Paired Domination is NP-complete on triangle-free \( d \) -regular graphs for each fixed \( d \ge 3 \) , and it does not admit a \( 2^{o(|V(G)|)} \) time algorithm unless ETH fails. Additionally, we establish that determining if the paired domination number coincides with the total domination number is NP-hard across planar bipartite subcubic graphs, planar cubic graphs, and triangle-free \( d \) -regular graphs.