Predicting the evolution of grain orientations and stress states in polycrystalline materials is essential for understanding material behaviors under mechanical loading. Traditional computational methods, such as crystal plasticity (CP) models and their algorithms (CP-FEM), are computationally expensive and require extensive resources, limiting their practical application in real-time material design and optimization. This study introduces a novel Graph Neural Network–Long Short-Term Memory (GNN-LSTM) multi-task learning framework to accurately and efficiently predict grain orientation evolution, as well as local (grain level) and global stress-strain responses under the plane-stress condition (including in-plane shear stresses), in polycrystalline materials. In this model, each grain in a representative volume element (RVE) is treated as a node in a graph, and the edges capture shared boundary information. The GNN layers are employed to aggregate features from adjacent grains, effectively modeling grain-to-grain interactions. Concurrently, LSTM layers capture the time-dependent history of deformation. A novel Dynamic State Refiner (DSR) is utilized to dynamically adjust the hidden states of nodes based on increments in strain, thereby enabling the model to consider the impact of deformation magnitude on updates to the microstructural state. Additionally, multi-task decoders are used to predict orientation evolution, along with local and global stresses, by leveraging a shared feature representation. An uncertainty-based loss function adaptively adjusts the weight of these tasks, preventing any single objective from dominating the training process. This GNN-LSTM framework efficiently handles extensive sequential data through truncated backpropagation in sub-sequences, while misorientation angle calculations ensure physically meaningful orientation predictions. The proposed framework achieves high-fidelity predictions with reduced computational effort by orders of magnitudes compared to crystal plasticity simulations. By integrating adjacency-aware GNNs, history-dependent LSTMs, DSR-mediated strain refinement, and uncertainty-based multi-task learning, the proposed approach offers a robust and scalable surrogate for computationally demanding microstructure evolution studies, paving the way for accelerated materials design and optimization.