Edge computing has been considered as one of the key paradigms in the fifth-generation (5G) networks for enabling computation-intensive yet latency-sensitive vehicular Internet services. In this paper, we investigate non-orthogonal multiple access (NOMA) assisted vehicular edge computing via underlay spectrum sharing, in which vehicular computing-users (VUs) form a NOMA-group and reuse conventional cellular user's (CU's) channel for computation offloading. In spite of the benefit of spectrum sharing, the resulting co-channel interference degrades the CU's transmission. We thus firstly focus on a single-cell scenario of two VUs reusing one CU's channel, and analyze the CU's increased delay due to sharing channel with the VUs. We then jointly optimize the VUs' partial offloading and the allocation of the communication and computing resources to minimize the VUs' delay while limiting the CU's suffered increased delay. An efficient layered-algorithm is proposed to tackle with the non-convexity of the joint optimization problem. Based on our study on the single-cell scenario, we further investigate the multi-cell scenario in which a group of VUs flexibly form pairs to reuse the channels of different CUs for offloading, and formulate an optimal pairing problem to minimize the VUs' overall-delay. To address the difficulty due to the combinatorial nature of the pairing problem, we propose a cross-entropy (CE) based probabilistic learning algorithm to find the optimal VU-pairings. Extensive numerical results are provided to validate the effectiveness and efficiency of our proposed algorithms for both the single-cell scenario and multi-cell scenario. The results also demonstrate that our NOMA-assisted MEC via spectrum sharing can outperform the conventional frequency division multiple access assisted offloading scheme.