Graph Edit Distance (GED) is a classical measure of similarity between two graphs, defined as the minimum number of edit operations required to transform one graph into another. Given that computing the exact GED value is an NP-hard problem, recent research focuses on GED estimation, while compared to traditional heuristics, significant performance improvement is achieved by leveraging representation learning techniques such as graph neural networks (GNNs). With an end-to-end framework, these algorithms model GED computation as a regression task but are unable to predict the edit path. Very recently, hybrid algorithms have emerged by combining the strengths of traditional and GNN-based algorithms to achieve better performance and interpretability, while the core issue, i.e., the cost estimation in the matching process, remains largely unexplored. In this paper, we propose a neuralized A* algorithm with fine-grained matching cost prediction (FineMatch), which focuses on the cost estimation of further operations during the A* searching process. Specifically, we decompose the estimated cost for the unmatched subgraphs into two terms, namely, the cost within the unmatched subgraphs and the cost of handling the border edges that bridge the matched and unmatched parts. We construct an end-to-end neural network model that considers cross-graph interactions and integrates local and global information to predict the cost of unmatched graph pairs. Moreover, we present a simple yet effective heuristic to compute a lower bound of the cost for matching border edges, as ignored by previous studies. Experimental results show the practical effectiveness of our approach, which outperforms state-of-the-art methods.