Try this,
ISNEW() && Service_Date__c <= today()
IsNew doesn't neeed any parameter. It returns true for insert and false for rest.
Validation rules apply any time a record is altered, whether that alteration takes place in Process Builder, the user interface, or the API. You can't intercept the validation rule's message and allow the update to complete successfully.
In a Process Builder or Flow context, one tactic you can use to allow an un-validated change to go through if and only if it's made via a specific automation is to build a check into your rule for a hidden field (not shown on any page layout, or hidden from users via FLS).
Say we have a Checkbox field Process_Builder_Update__c. Set this to true prior to making your updates. Then, in your validation rule, add a check for this field so that the rule does not evaluate to true when the field is set:
AND(NOT(Process_Builder_Update__c), EXISTING_VALIDATION_RULE)
Then, the validation rule won't go off when your process makes its updates, because it sets Process_Builder_Update__c, but it will still be in effect when your users make changes.
You'll also want to un-set the flag once you're finished, so that users can't bypass the validation rule with the flag still set. Your flow should finish by setting the field back to false.
This won't work if your flow leaves your records in an un-validatable state (where any change will fail the validation rule), because unsetting the field will fail. However, you really won't want to leave your records like that anyway, as it means any user update will fail.
Best Answer
First of all, the Validation Rule executes upon a DML event on an object. For argument's sake, we'll assume that object is
Obj1__cSo, as long as
Obj2__cis a parent object (via master-detail or lookup) toObj1__c, then the Validation Rule would look likeObj2__ris the relationship name fromObj1__ctoObj2__cNow, if
Obj2__cis not related toObj1__cvia a master or lookup relationship (parent/grandparent/great-grandparent or greatgreat-grandparent), then you can't do the Validation Rule.Validation Rules can't look down to children nor look up and then down to siblings.