Decoding gait dynamics from EEG signals presents significant challenges due to the complex spatial dependencies of motor processes, the need for accurate temporal and spectral feature extraction, and the scarcity of high-quality gait EEG datasets. To address these issues, we propose EEG2GAIT, a novel hierarchical graph-based model that captures multi-level spatial embeddings of EEG channels using a Hierarchical Graph Convolutional Network (GCN) Pyramid. To further improve decoding performance, we introduce a Hybrid Temporal-Spectral Reward (HTSR) loss function, which integrates time-domain, frequency-domain, and reward-based loss components. In addition, we contribute a new Gait-EEG Dataset (GED), consisting of synchronized EEG and lower-limb joint angle data collected from 50 participants across two laboratory visits. Extensive experiments demonstrate that EEG2GAIT with HTSR achieves superior performance on the GED dataset, reaching a Pearson correlation coefficient (r) of 0.959, a coefficient of determination of 0.914, and a Mean Absolute Error (MAE) of 0.193. On the MoBI dataset, EEG2GAIT likewise consistently outperforms existing methods, achieving an r of 0.779, a coefficient of determination of 0.597, and an MAE of 4.384. Statistical analyses confirm that these improvements are significant compared to all prior models. Ablation studies further validate the contributions of the hierarchical GCN modules and the proposed HTSR loss, while saliency analysis highlights the involvement of motor-related brain regions in decoding tasks. Collectively, these findings underscore EEG2GAIT's potential for advancing brain-computer interface applications, particularly in lower-limb rehabilitation and assistive technologies.