In privacy-preserving machine learning (PPML), homomorphic encryption (HE) has emerged as a significant primitive, allowing the use of machine learning (ML) models while protecting the confidentiality of input data. Although extensive research has been conducted on implementing PPML with HE by developing the efficient construction of private counterparts of ML models, the efficient HE implementation of embedding layers for token inputs such as words remains inadequately addressed. Thus, our study proposes an efficient algorithm for privacy-preserving embedding via look-up table evaluation with HE (HELUT) by developing an encrypted indicator function (EIF) that assures high precision with the use of the approximate HE scheme (CKKS). Based on the proposed EIF, we propose the CodedHELUT algorithm to facilitate an encrypted embedding layer for the first time. CodedHELUT leverages coded inputs to improve overall efficiency and optimize memory usage. Our comprehensive empirical analysis encompasses both synthetic tables and real-world large-scale word embedding models, including GloVe 6B50d and 42B300d. Notably, for GloVe-42300d, the CodedHELUT algorithm achieves an evaluation time of 14.448 seconds for the embedding layer while maintaining high precision (17 bits).