Calculate change denominations 3
1) is a Value Object "better" than a Domain Service?


This is certainly subjective, but i'll offer this pragmatic view point. Evaluate how often this code will be actively referenced and debugged by other developers. If this code is located in an easily reusable utility assembly, and it is a realistic expectation that it will be reused, then Value Object wins for me every time. It offers more self documentation than your initial attempt which is important because you have not implemented code comments at all. 
At the end of the day you have to justify the time and effort required to get the code into production, code that is reused a lot, especially by other developers is worth the effort to get it right, but you have increased you code surface and will have to increase you unit test coverage to match.
Value objects like this i find are much easier to unit test, and like you have said with validation, the object now has additional options for expressing it's state without blocking execution with exceptions and we can more easily inherit this structure and when we need to override specific functionality, such as validation when we as developers do reuse your code.


  2) Is it wise to have a property called Currency.DecimalPlaces


Absolutely, especially with currency where rounding errors can have a real world monetary impact on the user, this seems like a useful thing to know, and it is natural to expect that Currency would already have this attribute.


  3) Should I go with option 2?


See my response to question 1  from a purist point of view your Value Object is a complete package, it has a dependency on Currency, but is easier to lock down with unit tests and to distribute in a utility assembly for reuse. It's up to you to evaluate the cost of developing this solution and refactoring existing code to use it. 

Certainly follow the advice from @t3chb0t, you've gone to this much effort, implement your own contract definition for the response from CalculateDenominations, a key value pair response is too ambiguous for users know how to use the response, it's the missing bit of "self" documentation.


  How do i approach validation with option 1?


Throwing exceptions from the calculation routine is an acceptable method for validation, if this was a Mutable type (not readonly) then I would argue that it would be better than throwing exceptions from the constructor which can lead to other interesting and less than satisfactory implementation patterns. 


  UPDATE: Moving validation to an explicit method called Validate() further helps to self document your class, and makes it easier to maintain long term. You still call validation from either your calculation method or the constructor. As a bonus when validation fails, the stack trace will now show DenominationsRequired.Validate() which further describes why the exception was raised for future debuggers.


For mutable types it's only at the point of execution that the validation matters, the code that interacts with the instances of this class should be free to instantiate the object and react to its state at a later point in the execution. It is hard for example to check the state of a Value object if we failed to create the object in the first place.


  Here your Value type is an Immutable Type, that is to say that it's value over time will not change, and cannot because you have marked the fields as readonly. This is a special case where it is more appropriate to validate in the constructor rather than in the calculation because there will not be any opportunity to change the value if it is not valid.


A quick note about your validation, you hardcoded 2 as the comparison, rather than Currency.DecimalPlaces, so it should be:

if (decimal.Round(cost, currency.DecimalPlaces) != cost)
        throw new ArgumentException(string.Concat("Cost has too many decimal places.  It should only have: ", currency.DecimalPlaces), "Cost");