There's something at the heart of them that makes them interesting. It isn't just "exploration", but a particular style of exploration, which will not fail. It isn't just boss fights with dodging, because having that alone doesn't have the heart of a Souls game. The exploration alone could, but yeah, obviously it has to be done properly, not just "exploration".

Realistically, can't both combat and exploration be foundational elements of soulslike?

It could. I honestly don't think it is. Sekiro is also a Souls-like, and the combat is very different. I'm pretty confident you can make a good Souls-like with no combat. The combat, in my opinion, is there to give you a reason to explore. It's there to be a challenge, where exploring is the key to overcoming it. There will be items and secrets that make the combat easier if you search for it. It's not required, but you'd need something else to take the place of this.

Chants of Sennaar comes to mind of something I'd consider to capture a lot of the spirit of Souls games without combat. They're obviously very different games, but I think they share a lot. You can try to brute force your way through, but you're encouraged to explore and engage with the world, and discover it, which makes the critical path easier. This is the goal for both Souls-likes and CoS.

That's not what I meant. I meant that the core experience will be good if it replicates what the Souls games do, which is why they're successful. Many "Souls-likes" replicate the combat, and it sucks. Honestly, the DS1 and Demons Souls combat is pretty rough, but they revolutionized gaming, and the boss fights weren't the unique thing they were doing. Boss fights like them have existed forever.

If you look at the older FromSoftware catalogue, you can see what makes their games special. The older games have incredibly clunky combat, but they still have the core exploration loop. There's a hand built world with care and thought put into every detail, and the game gives obstacles that get easier if you engage with the world and explore. This is often with items or levels, but it's sometimes just with information. This is what makes a Souls-likes, and the copycats that fail are missing this (or they just didn't make an interesting world to explore). Hollow Knight isn't great because of the combat. The combat is fine, but it's the interesting world that's begging for you to engage with it that makes it compelling. That's the core of Souls-likes.