Kidney stone is a common urological disease in dogs and can lead to serious complications such as pyelonephritis and kidney failure. However, manual diagnosis involves a lot of burdens on radiologists and may cause human errors due to fatigue. Automated methods using deep learning models have been explored to overcome this limitation. Veterinary images present additional challenges due to the various sizes of organs depending on different species, with particularly poor performance on smaller lesions. These challenges suggest the need for a robust deep learning model that can accurately detect various sizes of kidney stones and kidneys. Moreover, public datasets with high-quality CT annotations for dog lesions and organs are almost not available. To address these challenges, we introduce a parallel frequency-spatial hybrid network (PFSH-Net), specifically designed for detecting kidney stones in CT images of dogs. The PFSH-Net consists of an encoder-decoder architecture that simultaneously captures spatial and frequency domain features. Moreover, we propose a multi-scale fusion (MSF) module that integrates low-level and high-level representations in the spatial and frequency domains. We collected a veterinary CT dataset with high-quality labels annotated by expert veterinary radiologists, and this dataset is referred to as the JBNU-ACT dataset. The effectiveness of the proposed method is demonstrated using a real-world dataset, with performance improvements of 4.1366, and 0.6234 on the HD, and ASD metrics, respectively. Moreover, the generalization of the model is evaluated on the publicly available BTCV dataset by achieving the average DSC score of 0.7960, which outperforms the previous method. Our code is available at https://github.com/gyeongyeon-Hwang/veterinary-kidney-segmentation.