Ensuring robust PPG-based heart-rate (HR) monitoring in presence of motion artifacts is an open challenge. Recent algorithms combine PPG and inertial signals to mitigate artifacts, but suffer from limited generality and have not been ported to MCUs. In this work, we propose the use of Temporal Convolutional Networks (TCN) for this task, using a Neural Architecture Search (NAS) method to derive a rich family of models. Among them, we obtain a TCN that outperforms the state-of-the art on a large open dataset, achieving a Mean Absolute Error (MAE) of just 3.84 Beats Per Minute (BPM). Furthermore, we also obtain a set of smaller networks that can be deployed on a MCU, requiring only 5k parameters and reaching a latency of 17.1ms while consuming just 0.21mJ per inference.